Submission #18981

#	Time	Username	Problem	Language	Result	Execution time	Memory
18981		tncks0121	카드 (kriii4_Z)	C++14	13 / 100	3000 ms	1868 KiB

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 / 13
• Subtask 2: 0 / 87