牛客寒假算法基础集训营2题解（C题）

对于这道C题，他要我们求的是在n道题目中，有0，1，2，3....n道题目做对的概率，然后分别按隔一个空格输出对1e9+7求模后的结果，在看了出题人的题解后，我一开始也十分困惑，因为出题人或其他提交的同学代码都没有解释，然后，我就花了一个小时在纸上模拟，终于我搞懂了，希望接下来的可以对报名参加了比赛但还没理解该题的同学有所帮助。
首先，我来解释一下下面几个代码的含义：
在代码中，我们先定义一个二维数组，f[2020][2020],对于f[i][j]的含义是在当前的i道题目中，恰好有j道题目做对的概率（以下所说的概率都是求模后的结果）。

const int mod=1e9+7;
(mod+1-p[i])%mod

该式的意义是第i题做错的概率。为了方便计算，我们都是假设分式a/b当中分母b的值为1，即b=1,（因为任何分式都可以化为分母为1的式子，当然，分子a可以为小数。所以由b*q%(1e9+7)=a;这里b=1，q就是我们输入的p[i],可得p[i]=kmod+a;即a=p[i]-kmod;那么求对应的错误的概率就是用1-a，即1-a=（kmod+1-p[i]）%mod=(mod+1-p[i])%mod,因为分母b为1；

f[i][0]=f[i-1][0]*(mod+1-p[i])%mod;

那么，该行代码的意思就是当前有i道题目，有0道做对的概率等于i-1道题目中有0道题目做对的概率再乘以第i道题目做错的概率。

f[i][j]=(f[i-1][j]*(mod+1-p[i])%mod+f[i-1][j-1]*p[i])%mod;

所以，这个代码就不难理解了。即要求i道题目中，j道题目做对的概率，就是相当于求i-1道题目中j道题目做对的概率乘以第i道题目做错的概率，再加上i-1道题目中j-1道题目做对的概率乘以第i道题目做对的概率（有点绕哈，希望大家好好理解）。其实这个算法思想和求排列组合的思想不谋而和。
接下来，我就给出代码了哦！

#include<iostream>
using namespace std;
const int mod=1e9+7;
long long p[2020],f[2020][2020];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    f[0][0]=1;  //0道题目做对0题的概率肯定是1 
    for(int i=1;i<=n;i++){
        //从题目1开始进行枚举到n 
        f[i][0]=f[i-1][0]*(mod+1-p[i])%mod;  //求有i道题目做对0道题目的概率 
        for(int j=1;j<=i;j++){
            f[i][j]=(f[i-1][j]*(mod+1-p[i])%mod+f[i-1][j-1]*p[i])%mod;  
            //由类推求出当前有i道题目中，做对j道题目的概率 
            //这里j从1开始进行枚举到当前循环下的i，
            //所以在这个过程中就求出来了有i题的情况下，做对0到i道题目的概率 
        }
    }
    for(int i=0;i<=n;i++){
        cout<<f[n][i];
        if(i<n)  cout<<" "; //为了按题目格式输出，希望这个方法还没学到的同学可以记住
    }
    return 0;
}

好了，这题的解题思路大概就是这样了，希望对刚接触小伙伴们有所帮助，接下来我还会继续给出另外几题的题解的，谢谢大家。我的博客目前主要是针对萌新的，（因为本人也是萌新一枚，所以更能理解）所以如果有牛客的大佬无意间看到希望可以提出宝贵的建议，当然，如果有不解的可以在下方留言，我会尽力去帮忙的。
附：
牛客寒假算法基础训练营2题解F题：https://blog.nowcoder.net/n/a6eb59c66675495da6d5d4697e5d7cf3
牛客寒假算法基础训练营2题解D题：https://blog.nowcoder.net/n/0140a8622eba4346b4811ea9c0749312