#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) {
for(int i = L; i >= 0; i--) {
mint t = 0;
for(int k = 0; k <= i; k++) t = t + p[i-k] * q[k];
p[i] = t;
}
};
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 multiply(coef, 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1859 ms |
1868 KB |
Output is correct |
2 |
Correct |
1945 ms |
1868 KB |
Output is correct |
3 |
Correct |
1320 ms |
1868 KB |
Output is correct |
4 |
Correct |
1928 ms |
1868 KB |
Output is correct |
5 |
Correct |
1693 ms |
1868 KB |
Output is correct |
6 |
Correct |
1506 ms |
1868 KB |
Output is correct |
7 |
Correct |
1675 ms |
1868 KB |
Output is correct |
8 |
Correct |
1665 ms |
1868 KB |
Output is correct |
9 |
Correct |
1754 ms |
1868 KB |
Output is correct |
10 |
Correct |
1483 ms |
1868 KB |
Output is correct |
11 |
Correct |
1719 ms |
1868 KB |
Output is correct |
12 |
Correct |
1449 ms |
1868 KB |
Output is correct |
13 |
Correct |
1705 ms |
1868 KB |
Output is correct |
14 |
Correct |
2104 ms |
1868 KB |
Output is correct |
15 |
Correct |
1707 ms |
1868 KB |
Output is correct |
16 |
Correct |
1541 ms |
1868 KB |
Output is correct |
17 |
Correct |
2112 ms |
1868 KB |
Output is correct |
18 |
Correct |
1679 ms |
1868 KB |
Output is correct |
19 |
Correct |
1785 ms |
1868 KB |
Output is correct |
20 |
Correct |
1778 ms |
1868 KB |
Output is correct |
21 |
Correct |
1447 ms |
1868 KB |
Output is correct |
22 |
Correct |
1510 ms |
1868 KB |
Output is correct |
23 |
Correct |
1198 ms |
1868 KB |
Output is correct |
24 |
Correct |
1449 ms |
1868 KB |
Output is correct |
25 |
Correct |
1573 ms |
1868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2552 ms |
1868 KB |
Output is correct |
2 |
Correct |
2463 ms |
1868 KB |
Output is correct |
3 |
Correct |
4858 ms |
1868 KB |
Output is correct |
4 |
Correct |
5994 ms |
1868 KB |
Output is correct |
5 |
Correct |
3772 ms |
1868 KB |
Output is correct |
6 |
Correct |
6090 ms |
1868 KB |
Output is correct |
7 |
Correct |
5934 ms |
1868 KB |
Output is correct |
8 |
Correct |
6002 ms |
1868 KB |
Output is correct |
9 |
Correct |
851 ms |
1868 KB |
Output is correct |
10 |
Correct |
2043 ms |
1868 KB |
Output is correct |
11 |
Correct |
2145 ms |
1868 KB |
Output is correct |
12 |
Correct |
2889 ms |
1868 KB |
Output is correct |
13 |
Correct |
3396 ms |
1868 KB |
Output is correct |
14 |
Correct |
2972 ms |
1868 KB |
Output is correct |
15 |
Correct |
3531 ms |
1868 KB |
Output is correct |
16 |
Correct |
2435 ms |
1868 KB |
Output is correct |
17 |
Correct |
2011 ms |
1868 KB |
Output is correct |
18 |
Correct |
6641 ms |
1868 KB |
Output is correct |
19 |
Correct |
6178 ms |
1868 KB |
Output is correct |
20 |
Correct |
7363 ms |
1868 KB |
Output is correct |