概率dp

概率dp

概率值为一个不可约分数\frac{a}{b}对模数mod取模的含义为：存在q使得b \times q\%mod=a，q就是\frac{a}{b}对mod取模的值。要把一个分式概率转化成模值时，要用到扩展欧几里得；若题目也直接给出模值，则不需要。
概率为0是，q为0；概率为1是，q为1。
那么当某个事件发生的概率为q时，它不发生的概率就是1-q，根据(q+1-q)=1，可以得出(q+1-q)\%mod=1，1-q=mod+1-q。
两个分式概率相乘时，直接乘就好了；模值意义下的概率也是直接乘，不过乘完之后要对mod再取一次模。
算概率
给出n道题模值意义下做对的概率，求这n道题中，总共作对0，1，...n到题的概率。
dp[i][j]表示前i道题中，做对j道的概率。
dp[i][j] = (dp[i-1][j]*(mod+1-p[i])+dp[i-1][j-1]*p[i])%mod

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 2e3+5;
ll ans[maxn][maxn];
ll n,p[maxn];
int main(){
    cin >> n;
    for (int i=1;i<=n;i++)
        cin >> p[i];
    ans[0][0] = 1;
    for (int i=1;i<=n;i++){
        ans[i][0] = ans[i-1][0]*(mod+1-p[i])%mod;
        for (int j=1;j<=i;j++){
            ans[i][j] = (ans[i-1][j]*(mod+1-p[i])+ans[i-1][j-1]*p[i])%mod;
        }
    }
    for (int i=0;i<=n;i++){
        printf("%lld",ans[n][i]);
        if (i!=n)   printf(" ");
    }
    return 0;
}

NC14734 比赛

概率以小数形式给出。
对于每道题，直接求通过的概率是比较难求的；可以容易求出不通过这道题的概率：d[i] = (1-a[i])*(1-b[i])*(1-c[i])
那么通过这道题的概率就是 1-d[i]

#include <bits/stdc++.h>
using namespace std;
double a[20], b[20], c[20], d[20], dp[20][20];
int main(){
    for (int i=1;i<=12;i++)    cin >> a[i];
    for (int i=1;i<=12;i++)    cin >> b[i];
    for (int i=1;i<=12;i++)    cin >> c[i];
    for (int i=1;i<=12;i++)
        d[i] = (1-a[i])*(1-b[i])*(1-c[i]);
    dp[0][0] = 1;
    for (int i=1;i<=12;i++){
        dp[i][0] = dp[i-1][0]*d[i];
        for (int j=1;j<=i;j++){
            dp[i][j] = dp[i-1][j]*d[i] + dp[i-1][j-1]*(1-d[i]);
        }
    }
    for (int i=0;i<=12;i++)
        printf ("%.6lf\n", dp[12][i]);
    return 0;
}