CF1540B-Tree Array【數學期望,dp】

正題

題目連結:https://www.luogu.com.cn/problem/CF1540B

題目大意

\(n\)個點的一棵樹，開始随機選擇一個點标記，然後每次随機選擇一個與被标記點連邊的點标記，按照标記順序排列，求期望逆序對數。

\(1\leq n\leq 200\)

解題思路

顯然是考慮兩個點\((x,y)\)産生的貢獻。

枚舉根，然後兩個點到根路徑上公共的部分沒有用，考慮不公共的部分一個長度為\(n\)，另一個長度為\(m\)，假設\(n\)先标記，此時我們可以枚舉\(n\)标記的時候\(m\)還有多少個沒标記的，機率就是

\[\frac{1}{2}\sum_{i=0}^{m-1}\binom{n-1+i}{i}\frac{1}{2}^{n-1+i}

\]

這個顯然可以用\(dp\)進行\(O(n^2)\)預處理。

然後在\(LCA\)處暴力枚舉點對就好了，時間複雜度：\(O(n^3)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=210,P=1e9+7;
struct node{
	ll to,next;
}a[N<<1];
ll n,tot,cnt,f[N][N],ls[N],v[N],dep[N],inv[N],ans;
void addl(ll x,ll y){
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;return;
}
void calc(ll x,ll fa,ll fr,ll L){
	v[++cnt]=x;ans+=x<fr;
	for(ll i=1;i<=L;i++){
		int n=dep[x]-dep[fr];
		int m=dep[v[i]]-dep[fr];
		if(v[i]>x)swap(n,m);
		(ans+=f[n-1][m-1]*inv[2]%P)%=P;
	}
	for(ll i=ls[x];i;i=a[i].next){
		ll y=a[i].to;
		if(y==fa)continue;
		calc(y,x,fr,L);
	}
	return;
}
void solve(ll x,ll fa){
	dep[x]=dep[fa]+1;
	for(ll i=ls[x];i;i=a[i].next){
		ll y=a[i].to;
		if(y==fa)continue;
		solve(y,x);
	}
	cnt=0;
	for(ll i=ls[x];i;i=a[i].next){
		ll y=a[i].to;
		if(y==fa)continue;
		calc(y,x,x,cnt);
	}
	return;
}
signed main()
{
	scanf("%lld",&n);inv[1]=1;
	for(ll i=2;i<=n;i++)inv[i]=P-inv[P%i]*(P/i)%P;
	f[0][0]=1;
	for(ll i=0;i<=n;i++)
		for(ll j=0;j<=n;j++){
			if(!i&&!j)continue;
			f[i][j]=((i?f[i-1][j]:0)+(j?f[i][j-1]:0))*inv[2]%P;
		}
	for(ll i=0;i<=n;i++)
		for(ll j=1;j<=n;j++)
			(f[i][j]+=f[i][j-1])%=P; 
	for(ll i=1,x,y;i<n;i++){
		scanf("%lld%lld",&x,&y);
		addl(x,y);addl(y,x);
	}
	for(ll i=1;i<=n;i++)
		solve(i,0);
	printf("%lld\n",ans*inv[n]%P);
	return 0;
}