Submission #18990

#	Time	Username	Problem	Language	Result	Execution time	Memory
18990		kriii	카드 (kriii4_Z)	C++14	100 / 100	622 ms	142060 KiB

Z

#include <stdio.h>

const long long mod = 1000000007;

long long pow(long long a, long long p)
{
	long long r = 1;
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

long long comb[3003][3003],sti[3003][3003],fact[3003],prv[3003],nxt[3003];
int cnt[11];

int main()
{
	int N,L;
	scanf ("%d %d",&N,&L);

	comb[0][0] = fact[0] = 1;
	for (int i=1;i<=L;i++){
		comb[i][i] = comb[i][0] = 1;
		for (int j=1;j<i;j++) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % mod;
		fact[i] = fact[i-1] * i % mod;
	}

	for (int i=0;i<N;i++){
		int d; scanf ("%d",&d); cnt[d]++;
	}

	prv[0] = 1;
	for (int i=1;i<=L;i++) prv[i] = prv[i-1] * cnt[0] % mod;
	for (int d=1;d<=10;d++) if (cnt[d]){
		sti[0][0] = 1;
		for (int i=1;i<=L;i++){
			for (int j=1;j<=cnt[d];j++){
				sti[i][j] = j * sti[i-1][j] % mod;
				if (i >= d) sti[i][j] = (sti[i][j] + comb[i-1][d-1] * sti[i-d][j-1]) % mod;
			}
		}

		for (int i=0;i<=L;i++) nxt[i] = 0;
		for (int i=0;i<=L;i++) for (int j=cnt[d]*d;i+j<=L;j++) nxt[i+j] = (nxt[i+j] + prv[i] * sti[j][cnt[d]] % mod * comb[i+j][j]) % mod;
		for (int i=0;i<=L;i++) prv[i] = nxt[i] * fact[cnt[d]] % mod;
	}

	printf ("%lld\n",prv[L]*pow(N,-L)%mod);

	return 0;
}

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