| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19939 |
2016-02-25T07:29:56 Z |
ainta |
능력 (kriii4_S) |
C++ |
|
1916 ms |
1396 KB |
#include<stdio.h>
long long BS = 1000000000, Mod = 1000000007;
int n, pv;
long long P[2][5010], D[2][5010], C[5010], Succ[5010], Fail[5010], Inv[5010];
long long Pow(long long a, long long b){
long long r = 1;
while(b){
if(b%2)r=r*a%Mod;
a=a*a%Mod;b/=2;
}
return r;
}
long long Invv(long long a){
return Pow(a,Mod-2);
}
int main(){
int i, j;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld %lld",&Succ[i],&C[i]);
Fail[i] = BS-Succ[i];
Inv[i] = Invv(i);
}
P[0][0]=1;
long long SS;
pv = 0;
for(i=1;i<=n;i++){
P[!pv][0]=P[pv][0]*BS%Mod;
for(j=1;j<=i;j++){
P[!pv][j] = (P[pv][j]*(i-j)%Mod*Inv[i]%Mod*BS + P[pv][j-1]*j%Mod*Inv[i]%Mod*Fail[i])%Mod;
}
for(j=0;j<i;j++){
D[!pv][j+1] = (Fail[i]%Mod*D[pv][j]%Mod*j + BS*D[pv][j+1]%Mod*(i-j-1) + Succ[i]*C[i]%Mod*P[pv][j])%Mod;
D[!pv][j+1] = D[!pv][j+1]*Inv[i]%Mod;
}
pv = !pv;
}
SS = 0;
for(i=1;i<=n;i++)SS = (SS+D[pv][i])%Mod;
printf("%lld\n",SS*Pow(Invv(BS),n)%Mod);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1396 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1396 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1396 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1396 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1903 ms |
1396 KB |
Output is correct |
| 2 |
Correct |
1909 ms |
1396 KB |
Output is correct |
| 3 |
Correct |
1916 ms |
1396 KB |
Output is correct |
| 4 |
Correct |
1905 ms |
1396 KB |
Output is correct |
| 5 |
Correct |
1901 ms |
1396 KB |
Output is correct |
| 6 |
Correct |
1897 ms |
1396 KB |
Output is correct |
| 7 |
Correct |
1898 ms |
1396 KB |
Output is correct |
| 8 |
Correct |
1908 ms |
1396 KB |
Output is correct |
| 9 |
Correct |
1902 ms |
1396 KB |
Output is correct |
| 10 |
Correct |
1910 ms |
1396 KB |
Output is correct |
| 11 |
Correct |
1896 ms |
1396 KB |
Output is correct |
| 12 |
Correct |
1889 ms |
1396 KB |
Output is correct |
| 13 |
Correct |
1896 ms |
1396 KB |
Output is correct |
| 14 |
Correct |
1893 ms |
1396 KB |
Output is correct |
| 15 |
Correct |
1904 ms |
1396 KB |
Output is correct |
| 16 |
Correct |
1893 ms |
1396 KB |
Output is correct |
| 17 |
Correct |
1909 ms |
1396 KB |
Output is correct |
| 18 |
Correct |
1893 ms |
1396 KB |
Output is correct |
| 19 |
Correct |
1878 ms |
1396 KB |
Output is correct |
| 20 |
Correct |
1904 ms |
1396 KB |
Output is correct |
