一、题目描述：
有 $n$ 个人，第 $i$ 个人一开始有 $a_i$ 个球。每个人都有一个自己的传球目标。
有一个正整数 $k$，从 $1\sim k$ 中随机选择一个数作为游戏的进行轮数。
在游戏的每一轮，所有人同时都把自己手上的球全部传给自己的传球目标。
求游戏结束之后，每个人手上的期望球的数量。答案对 $998244353$ 取模，保证有逆元存在。
数据范围：$1\le n\le 2\times 10^5,1\le k\le 1\times 10^{18}$。
二、解题思路：
首先我们发现这个期望可以转化为求和，最后乘上 $k$ 的逆元。
这类轮数很多的题有两条路可以走（就我的认知而言）：找规律 & 倍增
这题的状态显然：$f_{i,j}$ 表示节点 $i$ 经过 $2^j$ 轮之后获得的总贡献。
而转移的过程大概是比较套路的，但是这是我第一次做这样的题，所以还是分析一下：
令 $fa_{i,j}$ 表示节点 $i$ 的 $2^j$ 级祖先，$son_{i,j}$ 表示节点 $i$ 的 $2^j$ 级儿子。
画个图不难发现：$f_{i,j}=f_{i,j-1}+\sum f_{son_{i,j-1},j-1}$。这大概是很套路的，记下来就好。
虽然统计自己的儿子不好统计，但是只要每个点向自己的 $2^{j-1}$ 级祖先累加贡献就好了。
现在考虑经过了 $2^j$ 轮之后，$f_{i,j}$ 如何变化。其实也就是后面 $2^j$ 轮的贡献。
显然 $f'_{i,j}=f_{i,j+1}-f_{i,j}$ ，$f'_{i,j}=\sum f_{son_{i,j},j}$。
于是单次贡献也能 $O(n)$ 解决了，将 $k$ 二进制化，像快速幂一样统计答案，时间复杂度 $O(nlog_2^k)$。
三、完整代码：
1 #include<iostream> 2 #define N 200010 3 #define ll long long 4 #define mod 998244353 5 #define rep(i,l,r) for(ll i=l;i<=r;i++) 6 using namespace std; 7 ll n,k,inv,fa[N],val[N],tp[N],ans[N]; 8 ll ksm(ll base,ll q){ 9 ll res=1;base%=mod;while(q){ 10 if(q&1) res*=base,res%=mod; 11 base*=base;base%=mod;q>>=1; 12 }return res; 13 } 14 void add(ll &a,ll b){ 15 a+=b; if(a>=mod) a-=mod; 16 } 17 int main(){ 18 ios::sync_with_stdio(false); 19 cin.tie(0);cout.tie(0); 20 cin>>n>>k; inv=ksm(k,mod-2); 21 rep(i,1,n) cin>>fa[i]; 22 rep(i,1,n) cin>>val[i]; 23 rep(i,1,n) add(tp[fa[i]],val[i]); 24 rep(i,1,n) val[i]=tp[i]; 25 while(k){ 26 if(k&1){ 27 rep(i,1,n) add(ans[i],val[i]); 28 rep(i,1,n) tp[i]=0; 29 rep(i,1,n) add(tp[fa[i]],val[i]); 30 rep(i,1,n) val[i]=tp[i]; 31 } 32 rep(i,1,n) tp[i]=0; 33 rep(i,1,n) add(tp[fa[i]],val[i]); 34 rep(i,1,n) add(val[i],tp[i]); 35 rep(i,1,n) tp[i]=fa[fa[i]]; 36 rep(i,1,n) fa[i]=tp[i]; k>>=1; 37 } 38 rep(i,1,n) cout<<ans[i]*inv%mod<<" "; 39 return 0; 40 }
四、写题心得：
有一些倍增的题一直没时间写博客，今天总结一下：
$1、对于一个序列/图，若每个元素的后继不多于一个，那么就可以倍增 。=> Exp++!$
$2、倍增可以正序也可以倒叙，按情况选择。主要是看数组怎么样方便转移。=> Exp++!$