oj.uz

답안 #18981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18981 2016-02-17T01:59:04 Z tncks0121 카드 (kriii4_Z) C++14
13 / 100
 3000 ms 1868 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -