Submission #23223

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

HI

#include<cstdio>
#include<algorithm>
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;
}
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++){
        for(j=0;j<=S[i-1];j++){
            for(k=0;k<=S[n]-S[i];k++){
                D[i][j+k] = (D[i][j+k] + 1ll * D1[i-1][j] * D2[i+1][k]) % Mod;
            }
        }
    }
    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 'int main()':
HI.cpp:80:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
HI.cpp:82: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