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

题号留念。

Analysis

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

观察到每次重新分配后，威力总和不变。设

E_i^{(t)}

表示第

t

次爆炸后城市

i

的威力期望值。考虑一次爆炸的期望变化：

如果选中城市 $i$ ，概率为 $\frac{1}{n}$ ， $E_i^{(t+1)}=0$ 。
如果选中其他城市 $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

CPP

#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 一场空，不开【】见祖宗！！

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

文章操作

Analysis

Code

Ending

相关推荐

评论

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