算概率(取模处理dp)

https://ac.nowcoder.com/acm/contest/3003/C

链接:https://ac.nowcoder.com/acm/contest/3003/C
来源:牛客网

牛牛刚刚考完了期末,尽管 牛牛 做答了所有 n\text{}nn 道题目,但他不知道有多少题是正确的。
不过,牛牛 知道第 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;
}

 

 
上一篇:【JLOI2014】松鼠的新家


下一篇:P3605 [USACO17JAN]Promotion Counting晋升者计数