用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1

这是本文档旧的修订版!


Codeforces Round #706 (Div. 1)

B. Tree Array

题意

给定 $n$ 个点的树,点编号分别为 $1\sim n$。

初始时等概率随机选择一个点,接下来每次操作从未选择的且与已经选择的点相连的点中等概率随机选择一个点。

根据选择的顺序可以得到由点的编号构成的序列,问序列逆序对的期望个数。

题解

首先枚举初始选择点,并将初始选择点作为根节点。

不难发现,每个节点只有在所以祖先结点被选取后才有机会选取。

同时对任意点对 $(u,v)$,当 $p=\text{LCA}(u,v)$ 被选取后,他们的其余祖先节点被选取的概率总是相等的。

于是不妨设 $u\gt v,d_1=d_u-d_p,d_2=d_v-d_p$,于是 $(u,v)$ 构成逆序对的概率等价于如下模型:

两个袋子中分别有 $d_1,d_2$ 个球,每次有 $t$ 概率从某个袋子中选一个球,也有 $1-2t$ 概率无事发生,问 $d_2$ 个球的袋子先被取空的概率。

不难发现 $\text{dp}(d_1,d_2)=\cfrac {\text{dp}(d_1-1,d_2)+\text{dp}(d_1,d_2-1)}2$。然后暴力统计固定根每个点对贡献即可,时间复杂度 $O(n^3)$。

查看代码

查看代码

const int MAXN=205,mod=1e9+7;
int dp[MAXN][MAXN];
int quick_pow(int a,int k){
	int ans=1;
	while(k){
		if(k&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		k>>=1;
	}
	return ans;
}
struct Edge{
	int to,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt]=Edge{v,head[u]};
	head[u]=edge_cnt;
}
vector<int> ch[MAXN];
int dep[MAXN],ans;
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	ch[u].clear();
	ch[u].push_back(u);
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u);
		_for(j,0,ch[u].size())
		_for(k,0,ch[v].size()){
			int x=ch[u][j],y=ch[v][k];
			int d1=dep[max(x,y)]-dep[u],d2=dep[min(x,y)]-dep[u];
			ans=(ans+dp[d1][d2])%mod;
		}
		_for(j,0,ch[v].size())
		ch[u].push_back(ch[v][j]);
	}
}
int main()
{
	int inv2=quick_pow(2,mod-2);
	_for(i,1,MAXN)dp[0][i]=1;
	_for(i,1,MAXN)_for(j,1,MAXN)
	dp[i][j]=1LL*(dp[i-1][j]+dp[i][j-1])*inv2%mod;
	int n=read_int();
	_for(i,1,n){
		int u=read_int(),v=read_int();
		Insert(u,v);
		Insert(v,u);
	}
	_rep(i,1,n)
	dfs(i,0);
	enter(1LL*ans*quick_pow(n,mod-2)%mod);
	return 0;
}
2020-2021/teams/legal_string/jxm2001/contest/cf_728_div._1.1625487131.txt.gz · 最后更改: 2021/07/05 20:12 由 jxm2001