Submission #18981

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18981	2016-02-17T01:59:04 Z	tncks0121	카드 (kriii4_Z)	C++14	13 / 100	3000 ms	1868 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	1895 ms	1868 KB	Output is correct
2	Correct	1989 ms	1868 KB	Output is correct
3	Correct	1350 ms	1868 KB	Output is correct
4	Correct	1973 ms	1868 KB	Output is correct
5	Correct	1728 ms	1868 KB	Output is correct
6	Correct	1538 ms	1868 KB	Output is correct
7	Correct	1713 ms	1868 KB	Output is correct
8	Correct	1699 ms	1868 KB	Output is correct
9	Correct	1790 ms	1868 KB	Output is correct
10	Correct	1520 ms	1868 KB	Output is correct
11	Correct	1756 ms	1868 KB	Output is correct
12	Correct	1480 ms	1868 KB	Output is correct
13	Correct	1739 ms	1868 KB	Output is correct
14	Correct	2151 ms	1868 KB	Output is correct
15	Correct	1746 ms	1868 KB	Output is correct
16	Correct	1581 ms	1868 KB	Output is correct
17	Correct	2157 ms	1868 KB	Output is correct
18	Correct	1720 ms	1868 KB	Output is correct
19	Correct	1834 ms	1868 KB	Output is correct
20	Correct	1818 ms	1868 KB	Output is correct
21	Correct	1480 ms	1868 KB	Output is correct
22	Correct	1545 ms	1868 KB	Output is correct
23	Correct	1229 ms	1868 KB	Output is correct
24	Correct	1481 ms	1868 KB	Output is correct
25	Correct	1608 ms	1868 KB	Output is correct

Subtask #2

0.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2608 ms	1868 KB	Output is correct
2	Correct	2518 ms	1868 KB	Output is correct
3	Execution timed out	3000 ms	1864 KB	Program timed out
4	Halted	0 ms	0 KB	-