MinamiMelon
0%

期望DP_2021牛客暑期多校训练营4_B_Sample_Game

发表于

https://ac.nowcoder.com/acm/contest/11255/B

\[ \space \]

\(f(x)\) 当前选的数字为x，之后的选的数的数量(X)的期望

\(E(X)=f(x)=\sum_1^{x-1} p_i \cdot 1+p_x \cdot (1+f(x))+\sum_{x+1}^{n}(f(i)+1)\cdot p_i\)

\[ f(x)=\frac{1+\sum_{x+1}^{n}f(i)\cdot p_i}{1-p_x } \] 则总数量为（题目中用不到）

\[ E(X+1)=\sum_1^n p_i \cdot (1+f(i)) \]

形式上\(E(x)=\sum q_i \cdot c_i\)

\((X+1)^2\)的期望

\(E((X+1)^2)=\sum q_i \cdot (c_i+1)^2=\sum q_i \cdot ({c_i}^2+2c_i+1)=E(X^2)+2E(X)+1\)

\(g(x)\)为当前选的数字为x，之后得分(\(E(X^2)\))的期望

\(g(x)=\sum_1^{x-1} p_i \cdot 1+p_x \cdot(g(x)+2f(x)+1)+\sum_{x+1}^n p_i \cdot(g(i)+2f(i)+1)\)

\[ g(x)=\frac{\sum_1^{x-1} p_i \cdot 1+p_x \cdot(2f(x)+1)+\sum_{x+1}^n p_i \cdot(g(i)+2f(i)+1)}{1-p_x} \] \[ =\frac{1+p_x \cdot 2f(x)+\sum_{x+1}^n p_i \cdot(g(i)+2f(i))}{1-p_x} \]

则答案为

\[ E((X+1)^2)=\sum_1^n p_i \cdot (1+2f(i)+g(i)) \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mo=998244353;
const int N=105;
ll a[N],f[N],g[N];

ll inv(ll a){
	ll ans=1,p=mo-2;
	while(p){
		if(p&1) ans=(ans*a)%mo;
		a=(a*a)%mo;
		p>>=1;
	}
	return ans%mo;
}

int main(){
	ll n,S=0;
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		S+=a[i];
	}
	ll t=inv(S);
	for(ll i=1;i<=n;++i){
		a[i]=(a[i]*t)%mo;
	}
	S=0;
	for(ll i=n;i>0;--i){
		f[i]=(1+S)%mo*inv(1+mo-a[i])%mo;
		S=(S+f[i]*a[i]%mo)%mo;
		//cout<<f[i]<<endl;
	}
	S=0;
	for(ll i=n;i>0;--i){
		g[i]=(1+ 2*a[i]%mo*f[i]%mo + S)%mo * inv(1+mo-a[i])%mo;
		S=(S + a[i]*(g[i] + 2*f[i] %mo)%mo )%mo;
	}
	ll ans=0;
	for(ll i=1;i<=n;++i){
		ans=(ans+(1+2*f[i]%mo+g[i])*a[i]%mo)%mo;
	}
	printf("%lld",ans);
	return 0;
}