Codeforces 1172C1. Nauuo and Pictures (easy version)(期望DP)

题目链接：C1. Nauuo and Pictures (easy version)

题意：

一个网站共有$n$张图片，每张图片有权值$wi$，每次访问时看到第$i$张的概率为$\frac{wi}{{\sum }_{j=1}^{n}wj}$，其中$ai$为$1$表示$Nauuo$喜欢这张图片，为$0$表示不喜欢，$Nauuo$会访问$m$次网站，每次如果看到的是喜欢的图片就令其权值$+1$，是不喜欢的就令其权值$-1$,问访问$m$次后各图片权值的期望为多少

题解：

我们可以发现对每个$i$单独枚举其情况时，其他图片的权值我只需要知道喜欢和不喜欢权值的总和就行，不需要知道具体那一个的权值，这样我们就能把所以权值分成三类：
一类是我当前$i$的权值，一类是总的其他图片中我喜欢的权值和，一类是总的其他图片中我不喜欢的权值和。

首先我们预处理出所有初始权重$wi$的总和$sum$，所有我喜欢的图片的初始权重的总和$x$,和所有我不喜欢的图片的初始权重的总和$y$
我们用$dp[i][j][k][q]$表示对于第$i$张图片，当前一共访问了$j$次，$k$次访问的是我喜欢的图片，$q$次是当前图片的概率,那么我们将图片$i$按$a[i]$为$1$和为$0$分成两类:

$a[i]$为$1$:
1.当前遇到我喜欢的但不是第$i$张图片:
$dp[i][j][k][q]+=dp[i][j-1][k-1][q]\ast \frac{x+k-1-(w[i]+q)}{sum-(j-k)+k-1}$,$k\ge 1$
因为转移的状态$dp[i][j-1][k-1][q]$中遇到喜欢的有$k-1$次,所以遇到不喜欢的有$j-1-(k-1)$次，所以经过这$j$次后，当前总权值为$sum-(j-k)+k-1$,其中喜欢的权值增加了(k-1)，不喜欢的减少了$j-1-(k-1)$，因为当前遇到了$q$次图片$i$，所以图片$i$权值变为$wi+q$,因此喜欢的部分除去当前图片$i$的概率为$\frac{x+k-1-(w[i]+q)}{sum-(j-k)+k-1}$，（剩下的情都况按照这个模式转移就可以了）
2.遇到我喜欢的且当前是第$i$张图片
3.遇到我不喜欢的(因为$a[i]$为$1$，当前不可能是第$i$张)

$a[i]$为$0$:
（这里需要注意因为$a[i]$为$0$，所以$wi$的权值应当是减）
1.遇到我喜欢的($a[i]$为$0$，当前不可能是第$i$个)
2.遇到我不喜欢的但不是第$i$个
3.遇到我不喜欢的且是第$i$个

主要思路就是上面这样了，具体细节和实现可以参考代码和注释：

ll dp[52][52][52][52];//对于第i个，当前一共访问了j次，k次是我喜欢的，q次是当前点的概率
int a[52];
int w[52];
ll inv[3100];
ll mi(ll a,ll b){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%mod;
		}
		a=a*a%mod;
		b/=2;
	}
	return res;
}
void init(){
	inv[0]=1;
	for(int i=1;i<=3000;i++){
		inv[i]=mi(i,mod-2);
	}
}
ll ans[52];//对应期望
int main(){
/*cout<
/*cout<
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流
	int n,m;
	init();//求出inv逆元
	cin>>n>>m;
	ll sum=0;//总初始权值
	ll x=0,y=0;//总喜欢的初始权值，总不喜欢的初始权值
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		if(a[i]){
			x+=w[i];
		}
		else{
			y+=w[i];
		}
		sum+=w[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][0][0][0]=1;
		for(int j=1;j<=m;j++){
			for(int k=0;k<=j;k++){
				for(int q=0;q<=j;q++){
					if(a[i]){
						//遇到我喜欢的但不是第i个
						if(k>=1){
							(dp[i][j][k][q]+=(dp[i][j-1][k-1][q]*(x+k-1-(w[i]+q))%mod)*inv[sum-(j-k)+k-1]%mod)%=mod;
						}
						//遇到我喜欢的且是第i个
						if(k>=1&&q>=1){
							(dp[i][j][k][q]+=(dp[i][j-1][k-1][q-1]*(w[i]+q-1)%mod)*inv[sum-(j-k)+k-1]%mod)%=mod;
						}
						//遇到我不喜欢的(a[i]为1，当前不可能是第i个)
						(dp[i][j][k][q]+=(dp[i][j-1][k][q]*(y-(j-1-k))%mod)*inv[sum-(j-1-k)+k]%mod)%=mod;
					}
					else{
						if(q>j-k){
							continue;
						}
						//遇到我喜欢的(a[i]为0，当前不可能是第i个)
						if(k>=1){
							(dp[i][j][k][q]+=(dp[i][j-1][k-1][q]*(x+k-1)%mod)*inv[sum-(j-k)+k-1]%mod)%=mod;
						}
						//遇到我不喜欢的但不是第i个
						(dp[i][j][k][q]+=(dp[i][j-1][k][q]*(y-(j-1-k)-(w[i]-q))%mod)*inv[sum-(j-1-k)+k]%mod)%=mod;
						//遇到我不喜欢的且是第i个
						if(q>=1){
							(dp[i][j][k][q]+=(dp[i][j-1][k][q-1]*(w[i]-(q-1))%mod)*inv[sum-(j-1-k)+k]%mod)%=mod;
						}
					}
					if(j==m){//计算每个w的最终期望
						ll val=w[i];//w[i]的最终权值
						if(a[i]){
							val+=q;
						}
						else{
							val-=q;
						}
						if(val>=0){//小于0的情况是不合法的
							ans[i]=(ans[i]+dp[i][j][k][q]*val%mod)%mod;//对应期望，期望=权值*概率
						}
					}
				}
			}
		}
		cout<<ans[i]<<endl;
	}
	return 0;
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95