[关闭]
@Junlier 2018-10-30T22:15:32.000000Z 字数 2409 阅读 1766

洛谷P3412 仓鼠找题解(期望+统计论?)

题解
阅读体验:https://zybuluo.com/Junlier/note/1327573
原题链接:洛谷P3412 仓鼠找sugar II
好像只有洛谷有诶。。。

日常吐槽

这个期望题开发新思维方式还是比较好的。。。
毕竟还是很难想的。。。鸣谢教我做这个题!

题解来了

很容易发现答案就是是吧
但是不会在短时间内算分子部分啊。。。
但是我们可以发现:如果可以固定住终点,那么会很容易算
所以我们先钦定终点在,然后考虑某种方法来启发计算所有点为终点的情况

终点在

不妨把作为根
本来一个可以搞定,但是对正解毫无启发,所以再想一下
我们设表示从跳到的期望步数
那么有(这个自己思考一下就行了)(是儿子,是度数)

草稿纸上化简一下会得到
哇,这不是很美丽!得到的子树内)
突然发现数组只和子树度数和有关,嘿嘿、、、
这样也可以很方便地统计答案是吧:
说一下为什么,的边只会被的子树中节点去用走是吧,而全统计到了,所以直接乘

那么我们发现,固定一个点为终点时答案只和当前点为根时的子树大小×子树度数和 有关

拓展到终点随机

上面那个结论很重要
我们现在对每个点进行考虑,是不是它有很多个方向出去,那些方向都有可能有终点
我们分别计算那些终点是在哪一个方向

  1. 肯定还是先以为根把上面所需的所有东西处理出来
  2. 枚举每个点枚举边考虑根的方向
  3. 如果根在树中的的方向,就是方向,肯定有
    意思是对于根在方向有种位置,而每种位置此时贡献都是(上面说了的)
  4. 如果根在树中的某个儿子方向,就是方向,肯定有,含义的话根据方向的情况自己想一下吧

PS:上面这一段有不理解可以根据代码看
这样我们就统计完了总表达式的分子部分,乘个逆元就解决了。。。

  1. #include<bits/stdc++.h>
  2. #define il inline
  3. #define rg register
  4. #define ldb double
  5. #define lst long long
  6. #define rgt register int
  7. #define N 100050
  8. #define qw ljl[i].to
  9. #define MOD 998244353
  10. using namespace std;
  11. const int Inf=1e9;
  12. il int MAX(rgt x,rgt y){return x>y?x:y;}
  13. il int MIN(rgt x,rgt y){return x<y?x:y;}
  14. il int read()
  15. {
  16. int s=0,m=0;char ch=getchar();
  17. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  18. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  19. return m?-s:s;
  20. }
  21. int n;lst Ans;
  22. int hd[N],cnt,tot;
  23. int f[N],siz[N],fa[N],d[N];
  24. //f: the step's expectation of now jumps to fa[now] (as the root of 1)
  25. //f[now]=Σf[qw]+d[now]=totd[](in son_tree) 写题的时候写的傻逼英语。。。
  26. struct EDGE{int to,nxt;}ljl[N<<1];
  27. il void Add(rgt p,rgt q){ljl[++cnt]=(EDGE){q,hd[p]},hd[p]=cnt;}
  28. il void ADD(rg lst &x,rg lst y){x+=y;if(x>MOD)x-=MOD;}
  29. il int qpow(rg lst x,rgt y)
  30. {
  31. rg lst ret=1;
  32. while(y)
  33. {
  34. if(y&1)ret=(ret*x)%MOD;
  35. x=(x*x)%MOD,y>>=1;
  36. }return ret;
  37. }
  38. void Dfs(rgt now,rgt fm)
  39. {
  40. fa[now]=fm,siz[now]=1,f[now]=d[now];
  41. for(rgt i=hd[now];i;i=ljl[i].nxt)
  42. {
  43. if(qw==fm)continue;Dfs(qw,now);
  44. siz[now]+=siz[qw],f[now]+=f[qw];
  45. }
  46. }
  47. int main()
  48. {
  49. n=read();
  50. for(rgt i=1,p,q;i<n;++i)
  51. {
  52. p=read(),q=read();
  53. ++d[p],++d[q],Add(p,q),Add(q,p);
  54. }Dfs(1,0);
  55. for(rgt i=1;i<=n;++i)tot+=d[i];
  56. for(rgt now=1;now<=n;++now)
  57. for(rgt i=hd[now];i;i=ljl[i].nxt)
  58. {
  59. if(qw==fa[now])ADD(Ans,1LL*siz[now]*f[now]%MOD*(n-siz[now])%MOD);
  60. else ADD(Ans,1LL*(n-siz[qw])*(tot-f[qw])%MOD*siz[qw]%MOD);
  61. }
  62. return printf("%lld\n",Ans*qpow(1LL*n*n%MOD,MOD-2)%MOD),0;
  63. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注