2021牛客暑期多校训练营4

2021牛客暑期多校训练营4

B Sample Game

经典的期望dp，最后求得是平方可能会造成一些困扰。
设dp[i][0]代表选择了i之后步数的期望，dp[i][1]代表选择了i之后步数的平方的期望。

先考虑求出期望步数，枚举下次随机生成了哪一个数转移即可。
设\(sum=\sum w[i]\)
\(dp[i][0]=\sum_{j>=i} [\frac{w[j]}{sum}(dp[j][0]+1)]+\sum_{j
将式子中的dp[i][0]放在一边
\(\frac{sum-w[i]}{sum}dp[i][0]=\sum_{j>i} [\frac{w[j]}{sum}(dp[j][0]+1)]+\sum_{j
\(dp[i][0]=\frac{sum}{sum-w[i]}\{\sum_{j>i} [\frac{w[j]}{sum}(dp[j][0]+1)]+\sum_{j
预处理出\(\sum_{j，在dp过程中维护\(\sum_{j>=i} [\frac{w[j]}{sum}(dp[j][0]+1)]\)整个过程就是\(O(n)\)的

之后考虑如何求dp[i][1]
设\(dp[i][1]=\frac{\sum num_i^2} {n}\)，\(dp[i][0]=\frac{\sum num_i}{n}\)
\(num_i\)是第i种方案的步数，\(n\)是总方案数。
dp[i][1]也是像dp[i][0]那样转移的，所以我们要求出dp[i][1]+1(转移时将期望步数加1)即\(\frac{\sum (num_i+1)^2}{n}\)
\(\frac{\sum (num_i+1)^2}{n}=\frac{\sum (num_i^2+2num_i+1)}{n}=\frac{\sum num_i^2}{n}+2*\frac{\sum num_i}{n}+1=dp[i][1]+2dp[i][0]+1\)
最后统计答案时枚举第一个数随机生成哪一个。
最好的复杂度是\(O(n)\)，但是出题人给的范围是100。于是我是用\(O(n^2)\)写的。

#include
#include
#include
#include
#include
using namespace std;
#define p 998244353
#define int long long
#define N 150
int w[N],s[N],dp[N],Sum[N];
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
int ksm(int x,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*x%p;
		x=x*x%p;
		b>>=1;
	}
	return ans;
}
signed main(){
	int n=read();
	for(int i=1;i<=n;i++)w[i]=read(),Sum[i]=(Sum[i-1]+w[i])%p;
	for(int i=n;i>=1;i--){
		for(int j=1;j<=n;j++){
			int x=ksm((Sum[n]-w[i]+p)%p,p-2)%p*Sum[n]%p;
			int y=w[j]*ksm(Sum[n],p-2)%p;
			if(j=1;i--){
		for(int j=1;j<=n;j++){
			int x=ksm((Sum[n]-w[i]+p)%p,p-2)%p*Sum[n]%p;
			int y=w[j]*ksm(Sum[n],p-2)%p;
			if(j

#include
#include
#include
#include
#include
using namespace std;
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum*f;
}
struct node{
	int w,id;
}x[4];
bool cmp(node a,node b){
	return a.wb){
		swap(a,b);
		swap(s1,s3);
	}
	if(b>c){
		swap(b,c);
		swap(s2,s1);
	}
	if(a>b){
		swap(a,b);
		swap(s1,s3); 
	} 
	if(c-a+b>n){
		printf("NO");
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(i<=a)ans[s1][i]='a';
		else if(i>n-(c-a))ans[s1][i]='b';
		else ans[s1][i]='x';
	}
	for(int i=1;i<=n;i++){
		if(i<=b)ans[s2][i]='a';
		else ans[s2][i]='z';
	}
	for(int i=1;i<=n;i++){
		if(i<=b)ans[s3][i]='a';
		else if(i>n-(c-a))ans[s3][i]='b';
		else ans[s3][i]='y';
	} 
	for(int i=1;i<=3;i++){
		for(int j=1;j<=n;j++)cout<