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

· · 题解

题号留念。

Analysis

由于操作是线性的，我们可以直接分析期望值的演化。

观察到每次重新分配后，威力总和不变。设 E_i^{(t)} 表示第 t 次爆炸后城市 i 的威力期望值。考虑一次爆炸的期望变化：

  1. 如果选中城市 i，概率为 \frac{1}{n}，E_i^{(t+1)}=0。
  2. 如果选中其他城市 m，概率为 \frac{n-1}{n}，E_i^{(t+1)} = E_i^{(t)} + \frac{E_m^{(t)}}{n-1}。

因此：

E_i^{(t+1)} = \frac{1}{n} \cdot 0 + \frac{1}{n} \sum_{m \neq i} \left[ E_i^{(t)} + \frac{E_m^{(t)}}{n-1} \right]

化简得到：

E_i^{(t+1)} = \frac{n-1}{n} E_i^{(t)} + \frac{1}{n(n-1)} \sum_{m \neq i} E_m^{(t)}

令 S_E^{(t)} = \sum_{i=1}^n E_i^{(t)}。注意到 \sum_{m \neq i} E_m^{(t)} = S_E^{(t)} - E_i^{(t)}，代入得：

E_i^{(t+1)} = \frac{n-2}{n-1} E_i^{(t)} + \frac{S_E^{(t)}}{n(n-1)}

因为总期望 S_E^{(t)} 是常数，等于初始总威力 S，递推简化为：

E_i^{(t+1)} = p E_i^{(t)} + q

其中 p = \frac{n-2}{n-1}，q = \frac{S}{n(n-1)}。

解这个一阶线性递推，得到：

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

其中 p = \frac{n-2}{n-1}，S = \sum_{i=1}^n a_i。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxN=1e6+5,mod=998244353;
int n,k,a[maxN];
int qpow(int x,int y,int p){ //快速幂
    int r=1;
    while(y){
        if(y&1) (r*=x)%=p;
        (x*=x)%=p;
        y>>=1;
    }
    return r;
}
int inv(int x,int p){ //除法转化为乘逆元
    return qpow(x,p-2,p);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    int s=0;
    for(int i=1;i<=n;++i)
        cin>>a[i],(s+=a[i])%=mod;
    int p=(n-2+mod)%mod*inv(n-1,mod)%mod;
    int ppowk=qpow(p,k,mod);
    int sdivn=s*inv(n,mod)%mod;
    for(int i=1;i<=n;++i)
        cout<<(ppowk*a[i]%mod+sdivn*(1-ppowk+mod)%mod)%mod<<" ";
    return 0;
}

时间复杂度 \Theta(n + \log k)。

Ending

本题考查的数学知识为期望的概念，即每种情况的概率乘上答案然后求和，推导出线性的递推关系，通过发现总威力守恒简化式子。希望大家能通过此题和题解更好地掌握期望相关题目。

还有（最重要的）：十年 OI 一场空，不开【】见祖宗！！