Submission #23232

#	Time	Username	Problem	Language	Result	Execution time	Memory
23232		ainta	hi (KRIII5_HI)	C++14	2 / 7	500 ms	7920 KiB

HI

#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] = (A[i+K]+B[i])%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] = (A[i]-B[i]+Mod)%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 <= 70)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 (stderr)

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++) A[i+K] = (A[i+K]+B[i])%Mod;
              ^
HI.cpp: In function 'void Sub(std::vector<int>&, std::vector<int>&)':
HI.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<B.size();i++) A[i] = (A[i]-B[i]+Mod)%Mod;
              ^
HI.cpp: In function 'void Do()':
HI.cpp:93: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:127:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
HI.cpp:129:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&w[i]);
                          ^

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5