Submission #20058

#	Time	Username	Problem	Language	Result	Execution time	Memory
20058		Namnamseo	카드 (kriii4_Z)	C++14	13 / 100	137 ms	87912 KiB

Z

#include<cstdio>
#include<cstring>
long long po[3333],a,b,i,c,aa,bb=1,x,X=1e9+7,D[3333][3333];
long long pow(long long aa,long long bb){
    if(bb==0) return 1;
    long long ret=pow(aa,bb/2);
    ret=(ret*ret)%X;
    if(bb&1) ret=(ret*aa)%X;
    return ret;
}
long long f(long long C,long long L)
{
    if(D[C][L]>=0)return D[C][L];
    if(C==0&&L>=0)return D[C][L]=po[L];
    if(L==0)return D[C][L]=0;
    if(C>L)return D[C][L]=0;
    return D[C][L]=(C*f(C-1,L-1)%X+(a-C)*f(C,L-1)%X)%X;
}
main()
{
    memset(D,-1,sizeof(D));
    scanf("%lld%lld",&a,&b);
    for(i=1;i<=a;i++){scanf("%lld",&x);if(x==1)c++;};
    if(c==0)
    {
        printf("1");
        return 0;
    }
    po[0]=1;
    for(i=1;i<=b;i++)po[i]=po[i-1]*a%X;
    aa=f(c,b);
    printf("%lld",aa*pow(po[b],X-2)%X);
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 87