题解：P14514 [NFLSPC #8] 如何区分北京东路和北京东路

· · 题解

设总威力为 S，E_i(k) 表示经过 k 次爆炸后 i 威力的期望。我们考虑来求解期望的递推关系，也就是 E_i(k) 与 E_i(k-1) 的关系。

设第 k 次爆炸发生在 j，则分两种情况：

  1. 发生在 i。则 i 威力清零，贡献为 0。
  2. 发生在 j（j\neq i）。则 i 的威力增加 \frac{E_j(k-1)}{n-1}。

结合 S=\sum E_i(k-1)，得出递推公式：

E_i(k)=\frac{n-1}{n} E_i(k-1)+\frac{1}{n(n-1)}(S-E_i(k-1))=\frac{n-2}{n-1}E_i(k-1)+\frac{S}{n(n-1)}

之后可以矩阵加速，或者推出通项公式：

E_i(k)=(a_i-\frac{S}{n})(\frac{n-2}{n-1})^k+\frac{S}{n}

预处理一下之后可以做到 O(n) 求解。注意取模。

#include<iostream>
using namespace std;
#define int long long
const int N=1e6+10,mod=998244353;
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }
    return ans;
}
int a[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k,sum=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],sum=(sum+a[i])%mod;
    int x=sum*qpow(n,mod-2)%mod,y=qpow((n-2)*qpow(n-1,mod-2)%mod,k);
    for(int i=1;i<=n;i++) cout<<(x+(((a[i]-x)%mod+mod)%mod)*y%mod)%mod<<" ";
    return 0;
}