思路
用 f(i,j) 来表示当前做了i道题，共做对了j道题
状态 f[i][j] = f[i-1][j] * (1-p[i]) + f[i-1][j-1] * p[i]
第一种：由于i-1时对了j题，所以第i题做错了；
第二种：由于i-1时对了j-1题，所以第i题对了；
时间复杂度O（n^2)
CODE
1 #include <bits/stdc++.h> 2 #define dbg(x) cout << #x << "=" << x << endl 3 4 using namespace std; 5 typedef long long LL; 6 7 template<class T>inline void read(T &res) 8 { 9 char c;T flag=1; 10 while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; 11 while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; 12 } 13 14 namespace _buff { 15 const size_t BUFF = 1 << 19; 16 char ibuf[BUFF], *ib = ibuf, *ie = ibuf; 17 char getc() { 18 if (ib == ie) { 19 ib = ibuf; 20 ie = ibuf + fread(ibuf, 1, BUFF, stdin); 21 } 22 return ib == ie ? -1 : *ib++; 23 } 24 } 25 26 int qread() { 27 using namespace _buff; 28 int ret = 0; 29 bool pos = true; 30 char c = getc(); 31 for (; (c < '0' || c > '9') && c != '-'; c = getc()) { 32 assert(~c); 33 } 34 if (c == '-') { 35 pos = false; 36 c = getc(); 37 } 38 for (; c >= '0' && c <= '9'; c = getc()) { 39 ret = (ret << 3) + (ret << 1) + (c ^ 48); 40 } 41 return pos ? ret : -ret; 42 } 43 44 const int kmaxn = 1007; 45 LL f[kmaxn][kmaxn]; 46 const LL mod = 1e9 + 7; 47 int n; 48 LL p[kmaxn]; 49 50 int main() 51 { 52 scanf("%d",&n); 53 for(int i = 1; i <= n; ++i) { 54 scanf("%lld",&p[i]); 55 } 56 f[0][0] = 1; 57 for(int i = 1; i <= n; ++i) { 58 f[i][0] = f[i-1][0] * (mod+1-p[i]) % mod; 59 for(int j = 1; j <= n; ++j) { 60 f[i][j] = ((f[i-1][j]*(i-p[i]+mod)) % mod + f[i-1][j-1]*(mod+p[i]) % mod)% mod; 61 } 62 } 63 for(int i = 0; i < n; ++i) { 64 printf("%lld ",f[n][i]); 65 } 66 printf("%lld ",f[n][n]); 67 return 0; 68 }