AT_abc310_g 题解

yhy-trh / 2023-09-05 / 原文

一、题目描述：

　　有 $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 }