# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
23210 |
2017-05-04T18:02:27 Z |
ainta |
hi (KRIII5_HI) |
C++14 |
|
500 ms |
9276 KB |
#include<cstdio>
#include<algorithm>
using namespace std;
int P[110], Mod = 1000000007, n, w[60], F[5110], InvF[5110], C[110][110];
int D[128][5010], sum, Comb[5110][110], Num[60], TP[60][5010], CC[5110][110];
int Pow(int a, int b){
int r = 1;
while(b){
if(b&1)r=1ll*r*a%Mod;
a=1ll*a*a%Mod;b>>=1;
}
return r;
}
void Do(int nd, int b, int e, int sum){
if(b==e){
Num[b] = nd;
return;
}
int m = (b+e)>>1, i, j, k, ss = sum;
for(i=0;i<=sum;i++)TP[0][i] = D[nd][i];
for(i=1;i<=m-b+1;i++)for(j=0;j<=5000;j++)TP[i][j] = 0;
for(i=0;i<=m-b;i++){
for(j=0;j<=ss;j++){
for(k=1;k<=w[i+b];k++){
TP[i+1][j+k] = (TP[i+1][j+k] + 1ll * Comb[j+k][k] * C[w[i+b]][k] % Mod * TP[i][j])%Mod;
}
}
ss += w[b+i];
}
for(i=0;i<=ss;i++)D[nd+nd+1][i] = TP[m-b+1][i];
Do(nd+nd+1, m+1, e, ss);
for(i=0;i<=sum;i++)TP[0][i] = D[nd][i];
for(i=1;i<=e-m;i++)for(j=0;j<=5000;j++)TP[i][j] = 0;
ss = sum;
for(i=1;i<=e-m;i++){
for(j=0;j<=ss;j++){
for(k=1;k<=w[i+m];k++){
TP[i][j+k] = (TP[i][j+k] + 1ll * Comb[j+k][k] * C[w[i+m]][k] % Mod * TP[i-1][j])%Mod;
}
}
ss += w[m+i];
}
for(i=0;i<=ss;i++)D[nd+nd][i] = TP[e-m][i];
Do(nd+nd, b, m, ss);
}
int main(){
int i, j, k;
for(i=1;i<=100;i++){
int s = 0;
for(j=1;j<i;j++){
s = (s + 1ll * P[j]*(i-j))%Mod;
}
P[i] = (i - s + Mod)%Mod;
}
F[0]=1;
for(i=1;i<=5000;i++){
F[i]=1ll*F[i-1]*i%Mod;
}
InvF[5000] = Pow(F[5000], Mod-2);
for(i=5000;i>=1;i--)InvF[i-1] = 1ll*InvF[i]*i%Mod;
for(i=0;i<=5000;i++){
for(j=0;j<=i&&j<=100;j++)Comb[i][j] = 1ll*F[i]*InvF[j]%Mod*InvF[i-j]%Mod;
}
C[0][0] = 1;
for(i=0;i<100;i++){
for(j=0;j<=100;j++){
for(k=0;k+j<=100;k++){
C[j+k][i+1] = (C[j+k][i+1] + 1ll * C[j][i] * P[k])%Mod;
}
}
}
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
//w[i] = 50;
sum += w[i];
}
D[1][0] = 1;
Do(1, 1, n, 0);
if(n==1){
printf("%d\n",sum);
return 0;
}
int res = 0;
for(i=1;i<=sum;i++){
for(j=1;j<=100;j++){
}
}
for(i=1;i<=n;i++){
for(int ii = 1; ii <= sum;ii++){
if(!D[Num[i]][ii])continue;
for(j=1;j<=w[i];j++){
for(k=0;j+k<=w[i];k++){
res = (res + 1ll * D[Num[i]][ii] * j * j % Mod * Comb[ii+k-2][k] % Mod * C[w[i]-j][k])%Mod;
}
}
}
}
printf("%d\n",res);
}
Compilation message
HI.cpp: In function 'int main()':
HI.cpp:72:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
HI.cpp:74:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&w[i]);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
26 ms |
9276 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
9276 KB |
Output is correct |
2 |
Correct |
159 ms |
9276 KB |
Output is correct |
3 |
Correct |
313 ms |
9276 KB |
Output is correct |
4 |
Execution timed out |
500 ms |
9276 KB |
Execution timed out |
5 |
Halted |
0 ms |
0 KB |
- |