一、題目描述：
有 $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++!$
浙公網安備 33010602011771號