Submission #18980

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18980	2016-02-17T01:55:55 Z	tncks0121	카드 (kriii4_Z)	C++14	13 / 100	3000 ms	2004 KB

Z

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
#include <iostream>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

#define debug(format, ...) printf(format, __VA_ARGS__);

const ll MOD = (ll)1e9 + 7;

ll modpow (ll a, ll b) {
	a %= MOD;
	ll ret = 1;
	while(b > 0) {
		if(b & 1) ret = (ret * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	}
	return ret;
}

struct mint {
	ll val;
	mint(ll val = 0): val((val % MOD + MOD) % MOD) { }
	mint operator+(mint p) { return val + p.val; }
	mint operator-(mint p) { return val - p.val; }
	mint operator*(mint p) { return val * p.val; }
	mint operator/(mint p) { return val * modpow(p.val, MOD-2); }
};

int N, L;

const int N_ = 3050, L_ = 3050;
mint tb[L_], nxt[L_];

int D[N_];
int freq[N_];

mint invfac[L_], inv[L_], fac[L_];

int main() {
	assert(scanf("%d%d", &N, &L) == 2);
	assert(1 <= N && N <= 3000);
	assert(1 <= L && L <= 3000);
	for(int i = 1; i <= N; i++) {
		assert(scanf("%d", D+i) == 1);
		assert(0 <= D[i] && D[i] <= 10);
		++freq[D[i]];
	}

	sort(D+1, D+N+1);

	inv[1] = 1;
	for(int i = 2; i < L_; i++) {
		inv[i] = inv[MOD % i] * -(MOD / i);
	}

	invfac[0] = fac[0] = 1;
	for(int i = 1; i <= L; i++) {
		fac[i] = fac[i-1] * i;
		invfac[i] = invfac[i-1] * inv[i];
	}

	tb[0] = 1;
	for(int d = 0; d <= 10; d++) if(freq[d] > 0) {
		vector<mint> base(L+1, 0);
		for(int j = d; j <= L; j++) base[j] = invfac[j];

		auto multiply = [](vector<mint> p, vector<mint> q) {
			vector<mint> ret(L+1, 0);
			for(int i = 0; i <= L; i++) {
				for(int k = 0; k <= i; k++) 
					ret[i] = ret[i] + p[i-k] * q[k];
			}
			return ret;
		};

		vector<mint> coef, cur(L+1, 0);
		for(int j = d; j <= L; j++) cur[j] = invfac[j];

		for(int k = 0; (1<<k) <= freq[d]; k++) {
			if((freq[d] >> k) & 1) {
				if(coef.empty()) coef = cur;
				else coef = multiply(coef, cur);
			}
			cur = multiply(cur, cur);
		}

		for(int j = 0; j <= L; j++) {
			nxt[j] = 0;
			for(int k = 0; k <= j; k++)
				nxt[j] = nxt[j] + coef[j-k] * tb[k];
		}

		copy(nxt, nxt + L + 1, tb);

	}

	mint ans = tb[L] * fac[L] / modpow(N, L);
	printf("%lld\n", ans.val);

	return 0;
}

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1896 ms	2000 KB	Output is correct
2	Correct	1986 ms	2000 KB	Output is correct
3	Correct	1347 ms	1868 KB	Output is correct
4	Correct	1973 ms	2000 KB	Output is correct
5	Correct	1726 ms	1868 KB	Output is correct
6	Correct	1538 ms	1868 KB	Output is correct
7	Correct	1711 ms	1996 KB	Output is correct
8	Correct	1698 ms	1868 KB	Output is correct
9	Correct	1789 ms	2000 KB	Output is correct
10	Correct	1512 ms	1868 KB	Output is correct
11	Correct	1757 ms	1996 KB	Output is correct
12	Correct	1476 ms	1868 KB	Output is correct
13	Correct	1739 ms	1868 KB	Output is correct
14	Correct	2143 ms	2000 KB	Output is correct
15	Correct	1743 ms	1868 KB	Output is correct
16	Correct	1570 ms	1868 KB	Output is correct
17	Correct	2152 ms	2000 KB	Output is correct
18	Correct	1716 ms	1868 KB	Output is correct
19	Correct	1828 ms	2000 KB	Output is correct
20	Correct	1816 ms	1868 KB	Output is correct
21	Correct	1477 ms	2004 KB	Output is correct
22	Correct	1542 ms	2004 KB	Output is correct
23	Correct	1224 ms	2004 KB	Output is correct
24	Correct	1478 ms	2004 KB	Output is correct
25	Correct	1607 ms	2004 KB	Output is correct

Subtask #2

0.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2604 ms	1868 KB	Output is correct
2	Correct	2507 ms	2000 KB	Output is correct
3	Execution timed out	3000 ms	1996 KB	Program timed out
4	Halted	0 ms	0 KB	-