| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 21290 |
2017-04-12T12:55:57 Z |
gs14004 |
능력 (kriii4_S) |
C++11 |
|
229 ms |
393544 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
lint ipow(lint x, lint p){
lint ret = 1, piv = x % mod;
while(p){
if(p&1) ret *= piv;
piv *= piv;
ret %= mod;
piv %= mod;
p >>= 1;
}
return ret % mod;
}
int n;
lint p[5005], d[5005], fact[5005];
lint dp[2][5005][5005];
int main(){
cin >> n;
lint ans = 0;
fact[0] = 1;
for(int i=1; i<=n; i++){
fact[i] = fact[i-1] * i % mod;
cin >> p[i] >> d[i];
p[i] *= ipow(1000000000, mod - 2);
p[i] %= mod;
}
dp[0][0][0] = 1;
for(int i=1; i<=n; i++){
for(int j=0; j<=n; j++){
dp[0][i][j] = dp[0][i-1][j];
if(j > 0) dp[0][i][j] += dp[0][i-1][j-1] * (mod + 1 - p[i]);
dp[0][i][j] %= mod;
dp[1][i][j] = dp[1][i-1][j] + dp[0][i-1][j] * (p[i] * d[i] % mod);
if(j > 0) dp[1][i][j] += dp[1][i-1][j-1] * (mod + 1 - p[i]);
dp[1][i][j] %= mod;
}
}
lint ret = 0;
for(int i=0; i<n; i++){
ret += dp[1][n][i] * (fact[i] * fact[n-1-i] % mod) % mod;
ret %= mod;
}
ret *= ipow(fact[n], mod - 2);
ret %= mod;
cout << ret;
}
Compilation message
S.cpp: In function 'int main()':
S.cpp:26:7: warning: unused variable 'ans' [-Wunused-variable]
lint ans = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 2 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 3 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 4 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 5 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 6 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 7 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 8 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 9 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 10 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 11 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 12 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 13 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 14 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 15 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 16 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 17 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 18 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 19 |
Correct |
0 ms |
393544 KB |
Output is correct |
| 20 |
Correct |
0 ms |
393544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
393544 KB |
Output is correct |
| 2 |
Correct |
219 ms |
393544 KB |
Output is correct |
| 3 |
Correct |
186 ms |
393544 KB |
Output is correct |
| 4 |
Correct |
189 ms |
393544 KB |
Output is correct |
| 5 |
Correct |
226 ms |
393544 KB |
Output is correct |
| 6 |
Correct |
183 ms |
393544 KB |
Output is correct |
| 7 |
Correct |
179 ms |
393544 KB |
Output is correct |
| 8 |
Correct |
209 ms |
393544 KB |
Output is correct |
| 9 |
Correct |
229 ms |
393544 KB |
Output is correct |
| 10 |
Correct |
229 ms |
393544 KB |
Output is correct |
| 11 |
Correct |
219 ms |
393544 KB |
Output is correct |
| 12 |
Correct |
206 ms |
393544 KB |
Output is correct |
| 13 |
Correct |
196 ms |
393544 KB |
Output is correct |
| 14 |
Correct |
209 ms |
393544 KB |
Output is correct |
| 15 |
Correct |
223 ms |
393544 KB |
Output is correct |
| 16 |
Correct |
196 ms |
393544 KB |
Output is correct |
| 17 |
Correct |
183 ms |
393544 KB |
Output is correct |
| 18 |
Correct |
196 ms |
393544 KB |
Output is correct |
| 19 |
Correct |
179 ms |
393544 KB |
Output is correct |
| 20 |
Correct |
189 ms |
393544 KB |
Output is correct |
