Submission #23222

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

HI

#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], Comb[5110][110], Num[60], TP[60][5010], 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 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);
    int sum = 0;
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
        sum += w[i];
    }
    D[1][0] = 1;
    Do(1, 1, n, 0);
    if(n==1){
        printf("%d\n",sum);
        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 <= sum;ii++){
            if(!D[Num[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[Num[i]][ii])%Mod;
        }
    }
    printf("%d\n",res);
}

Compilation message (stderr)

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:75: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