2020牛客寒假算法基础集训营2-C 算概率

题目链接 https://ac.nowcoder.com/acm/contest/3003/C
题目就是有个模意义下的概率有点绕，其实没啥，把它当作分数的概率，每次注意 +mod 和 %mod就行了。
思路是dp，转移:dp[i][j]=dp[i-1][j](1-a[i])+dp[i-1][j-1]a[i]-----a[i]是概率，dp[i][j]是前i题对j题的概率。很容易看出来。
代码如下：

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>

#define lson  rt << 1
#define rson  rt << 1 | 1
#define il inline
#define ll long long
#define LL long long
using namespace std;
const int maxn = 2000 + 10;
const ll inf = 0x7ffffffffff;
const ll mod = 1e9 + 7;

template<class T>
inline void read(T &res) {
    char c;
    T flag = 1;
    while ((c = getchar()) < '0' || c > '9')if (c == '-')flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')res = res * 10 + c - '0';
    res *= flag;
}

ll t;

ll qpow(ll a, ll b) {
    ll ans = 1;;
    a %= mod;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans % mod;
}
ll a[maxn],dp[maxn][maxn];
int main() {
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++) read(a[i]);
    dp[1][0]=(1-a[1]+mod)%mod;
    dp[1][1]=(a[1]+mod)%mod;
//    cout<<dp[1][0]<<' '<<dp[1][1]<<endl;
    for(ll i=2;i<=n;i++){
        for(ll j=0;j<=i;j++){
            dp[i][j]=(dp[i-1][j]*(1-a[i]+mod)%mod+dp[i-1][j-1]*a[i]+mod)%mod;
        }
    }
    for(ll i=0;i<=n;i++){
        cout<<dp[n][i]<<' ';
    }
    return 0;
}