Submission #19936

#TimeUsernameProblemLanguageResultExecution timeMemory
19936ainta능력 (kriii4_S)C++98
10 / 100
2000 ms393428 KiB
#include<stdio.h> long long BS = 1000000000, Mod = 1000000007; int n; long long P[5010][5010], D[5010][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; for(i=1;i<=n;i++){ P[i][0]=P[i-1][0]*BS%Mod; for(j=1;j<=i;j++){ P[i][j] = (P[i-1][j]*(i-j)%Mod*Inv[i]%Mod*BS%Mod + P[i-1][j-1]*j%Mod*Inv[i]%Mod*Fail[i]%Mod)%Mod; } for(j=0;j<i;j++){ D[i][j+1] = (Fail[i]%Mod*D[i-1][j]%Mod*j%Mod + BS*D[i-1][j+1]%Mod*(i-j-1)%Mod + Succ[i]*C[i]%Mod*P[i-1][j])%Mod; D[i][j+1] = D[i][j+1]*Inv[i]%Mod; } } SS = 0; for(i=1;i<=n;i++)SS = (SS+D[n][i])%Mod; printf("%lld\n",SS*Pow(Invv(BS),n)%Mod); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...