| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 23233 |
2017-05-05T10:44:00 Z |
ainta |
hi (KRIII5_HI) |
C++14 |
|
500 ms |
7924 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int P[110], Mod = 1000000007, n, w[60], F[5110], InvF[5110], C[110][110], S[60];
int D1[60][5010], D2[60][5010], D[60][5010], Comb[5110][110], CC[110][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;
}
vector<int> multiply(vector<int> &A, vector<int> &B){
int i, j, an = A.size(), bn = B.size();
vector<int> C(an+bn-1, 0);
for(i=0;i<an;i++)for(j=0;j<bn;j++)C[i+j]=(C[i+j]+(long long)A[i]*B[j])%Mod;
return C;
}
void Add(vector<int> &A, vector<int> &B, int K){
A.resize(max(A.size(), B.size() + K));
int i;
for(i=0;i<B.size();i++){
A[i+K] += B[i];
if(A[i+K] >= Mod)A[i+K] -= Mod;
}
}
void Sub(vector<int> &A, vector<int> &B){
A.resize(max(A.size(), B.size()));
int i;
for(i=0;i<B.size();i++){
A[i] -= B[i];
if(A[i] < 0)A[i] += Mod;
}
}
vector<int> Karatsuba(vector<int> &A, vector<int> &B){
int an = A.size(), bn = B.size();
if(an < bn)return Karatsuba(B, A);
if(A.empty() || B.empty())return vector<int>();
if(bn <= 50)return multiply(A, B);
int half = an / 2;
vector<int> A1(A.begin(), A.begin() + half);
vector<int> A2(A.begin() + half, A.end());
vector<int> B1(B.begin(), B.begin() + min(half,bn));
vector<int> B2(B.begin() + min(half,bn), B.end());
vector<int> C2 = Karatsuba(A2, B2);
vector<int> C0 = Karatsuba(A1, B1);
Add(A1, A2, 0); Add(B1, B2, 0);
vector<int> C1 = Karatsuba(A1, B1);
Sub(C1, C0);
Sub(C1, C2);
vector<int> ret;
Add(ret, C0, 0);
Add(ret, C1, half);
Add(ret, C2, half+half);
return ret;
}
void Do(){
int i, j, k, ss = 0;
D1[0][0] = 1;
for(i=1;i<=n;i++){
for(j=0;j<=ss;j++){
for(k=1;k<=w[i];k++){
D1[i][j+k] = (D1[i][j+k] + 1ll * Comb[j+k][k] * C[w[i]][k] % Mod * D1[i-1][j])%Mod;
}
}
ss += w[i];
}
ss = 0;
D2[n+1][0] = 1;
for(i=n;i>=1;i--){
for(j=0;j<=ss;j++){
for(k=1;k<=w[i];k++){
D2[i][j+k] = (D2[i][j+k] + 1ll * Comb[j+k][k] * C[w[i]][k] % Mod * D2[i+1][j])%Mod;
}
}
ss += w[i];
}
for(i=0;i<=n+1;i++){
for(j=0;j<=ss;j++){
D1[i][j] = 1ll * D1[i][j] * InvF[j]%Mod;
D2[i][j] = 1ll * D2[i][j] * InvF[j]%Mod;
}
}
for(i=1;i<=n;i++){
vector<int>AA, BB, CC;
for(j=0;j<=S[i-1];j++){
AA.push_back(D1[i-1][j]);
}
for(j=0;j<=S[n]-S[i];j++){
BB.push_back(D2[i+1][j]);
}
CC = Karatsuba(AA,BB);
for(j=0;j<CC.size();j++)D[i][j] = CC[j];
}
for(i=1;i<=n;i++){
for(j=0;j<=ss;j++){
D[i][j] = 1ll*D[i][j]* F[j]%Mod;
}
}
}
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]);
S[i] = S[i-1] + w[i];
}
D[1][0] = 1;
Do();
if(n==1){
printf("%d\n", S[n]);
return 0;
}
for(i=1;i<=100;i++){
for(j=1;j<i;j++){
for(k=1;k+j<=i;k++){
CC[i][j] = (CC[i][j] + 1ll*k*k*C[i-k][j])%Mod;
}
}
}
int res = 0;
for(i=1;i<=n;i++){
for(int ii = 1; ii <= S[n];ii++){
if(!D[i][ii])continue;
int ss = w[i] * w[i];
for(j=1;j<w[i];j++){
ss = (ss + 1ll * Comb[ii + j - 2][j] * CC[w[i]][j])%Mod;
}
res = (res + 1ll * ss * D[i][ii])%Mod;
}
}
printf("%d\n",res);
}
Compilation message
HI.cpp: In function 'void Add(std::vector<int>&, std::vector<int>&, int)':
HI.cpp:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<B.size();i++){
^
HI.cpp: In function 'void Sub(std::vector<int>&, std::vector<int>&)':
HI.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<B.size();i++){
^
HI.cpp: In function 'void Do()':
HI.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<CC.size();j++)D[i][j] = CC[j];
^
HI.cpp: In function 'int main()':
HI.cpp:133:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
HI.cpp:135: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 |
Correct |
23 ms |
7788 KB |
Output is correct |
| 2 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 3 |
Correct |
23 ms |
7788 KB |
Output is correct |
| 4 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 5 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 6 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 7 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 8 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 9 |
Correct |
19 ms |
7788 KB |
Output is correct |
| 10 |
Correct |
23 ms |
7788 KB |
Output is correct |
| 11 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 12 |
Correct |
23 ms |
7788 KB |
Output is correct |
| 13 |
Correct |
19 ms |
7788 KB |
Output is correct |
| 14 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 15 |
Correct |
19 ms |
7788 KB |
Output is correct |
| 16 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 17 |
Correct |
19 ms |
7788 KB |
Output is correct |
| 18 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 19 |
Correct |
26 ms |
7788 KB |
Output is correct |
| 20 |
Correct |
23 ms |
7788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
7788 KB |
Output is correct |
| 2 |
Correct |
33 ms |
7788 KB |
Output is correct |
| 3 |
Correct |
49 ms |
7788 KB |
Output is correct |
| 4 |
Correct |
99 ms |
7788 KB |
Output is correct |
| 5 |
Correct |
136 ms |
7788 KB |
Output is correct |
| 6 |
Correct |
206 ms |
7920 KB |
Output is correct |
| 7 |
Correct |
289 ms |
7920 KB |
Output is correct |
| 8 |
Correct |
356 ms |
7924 KB |
Output is correct |
| 9 |
Correct |
483 ms |
7920 KB |
Output is correct |
| 10 |
Execution timed out |
500 ms |
7920 KB |
Execution timed out |
| 11 |
Halted |
0 ms |
0 KB |
- |
