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

设总威力为

S

，

E_i(k)

表示经过

k

次爆炸后

i

威力的期望。我们考虑来求解期望的递推关系，也就是

E_i(k)

与

E_i(k-1)

的关系。

设第

k

次爆炸发生在

j

，则分两种情况：

发生在 $i$ 。则 $i$ 威力清零，贡献为 0。
发生在 $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)

求解。注意取模。

CPP

#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;
}

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

文章操作

相关推荐

评论

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