正题

题目链接:https://www.luogu.com.cn/problem/CF1540B

---

题目大意

$n$个点的一棵树，开始随机选择一个点标记，然后每次随机选择一个与被标记点连边的点标记，按照标记顺序排列，求期望逆序对数。

$1\le n\le 200$

---

解题思路

显然是考虑两个点$(x,y)$产生的贡献。

枚举根，然后两个点到根路径上公共的部分没有用，考虑不公共的部分一个长度为$n$，另一个长度为$m$，假设$n$先标记，此时我们可以枚举$n$标记的时候$m$还有多少个没标记的，概率就是
$$\frac{1}{2}\sum _{i=0}^{m-1}\left(\genfrac{}{}{0ex}{}{n-1+i}{i}\right){\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; }

总结

以上是生活随笔为你收集整理的CF1540B-Tree Array【数学期望,dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。