https://ac.nowcoder.com/acm/contest/3003/C
链接:https://ac.nowcoder.com/acm/contest/3003/C
来源:牛客网
不过,牛牛 知道第 i\text{}ii 道题的正确率是 pip_ipi。
牛牛 想知道这 n 题里恰好有 0,1,…,n0,1,\dots,n0,1,…,n 题正确的概率分别是多少,对 109+710^9+7109+7 取模。
对 109+710^9+7109+7 取模的含义是:对于一个 b≠0b\neq 0b=0 的不可约分数 aba\over bba,存在 q\text{}qq 使得 b×q mod (109+7)=ab\times q \bmod (10^9+7) =ab×qmod(109+7)=a,q\text{}qq 即为 aba\over bba 对 109+710^9+7109+7 取模的结果。
输入描述:
第一行,一个正整数 n\text{}nn 。
第二行,n\text{}nn 个整数 p1,p2,…,pnp_1,p_2,\dots,p_np1,p2,…,pn,在模 109+710^9+7109+7 意义下给出。
保证 1≤n≤20001\leq n\leq 20001≤n≤2000。
输出描述:
输出一行 n+1\text{}n+1n+1 个用空格隔开的整数表示答案(对 109+710^9+7109+7 取模)。示例1
输入
1 500000004
输出
500000004 500000004
说明
有 1 道题,做对的概率是 121 \over 221 ( 121 \over 221 在模 109+710^9+7109+7 意义下为 500000004 )。
#include <bits/stdc++.h> using namespace std; const int N = 2005, mod = 1e9 + 7; long long n, p[N], f[N][N]; int main() { cin >> n; for (int i = 1; i <= n; ++i) cin >> p[i]; for (int i = f[0][0] = 1; i <= n; ++i) { f[i][0] = f[i - 1][0] * (mod + 1 - p[i]) % mod; for (int j = 1; j <= i; ++j) f[i][j] = (f[i - 1][j] * (mod + 1 - p[i]) + f[i - 1][j - 1] * p[i]) % mod; } for (int i = 0; i <= n; ++i) cout << f[n][i] << ' '; return 0; }