牛客2020寒假训练营2-C

牛客2020寒假训练营2-C

七月 15, 2020

C.算概率

题意
有n道题
给出每到题做对的概率pi (取模1e9+7的意义下的pi)
问n道题答对 0 1 2 3 4…..n道的概率mod 1e9+7
如做对的概率为p=1/2 在mod 1e9+7 的意义下为p’=500000004
///没有对小数或分数的取模的概念 只有转化为除法取模
p=a/b在mod1e9+7的意义下的值为p’ p’ × b mod 1e9+7==a
某数x乘概率p 再取mod == x×a/b mod 1e9+7 除法取模等于乘逆元
上式== x×a×b的逆 mod 1e9+7 而a×b的逆==p’ 即p在mod1e9+7意义下的值
1-p 在mod 1e9+7意义下 =1-p’+mod

题解

​fi,j 表示前 i道题做对 j道的概率 转移时考虑第 j 道题是否做对,
转移方程为f{i,j}=f{i−1,j}×(1−pi)+f{i−1,j−1}×pi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

ll dp[2005][2005];
ll data[2005];
const ll mod=(ll)1e9+7;
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>data[i];
dp[0][0]=1;//dp[1][0]=(mod+1-data[1]);dp[1][1]=data[1];
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
if(j!=0)dp[i][j]=((dp[i-1][j-1]*data[i])%mod+(dp[i-1][j]*(mod+1-data[i]))%mod)%mod;
else dp[i][j]=dp[i-1][j]*(mod+1-data[i])%mod;
}
}
for(int i=0;i<=n;i++)cout<<dp[n][i]<<" ";
}