| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19016 |
2016-02-17T04:16:39 Z |
tncks0121 |
카드 (kriii4_Z) |
C++14 |
|
3373 ms |
4844 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;
int D[N_];
int freq[N_];
mint invfac[L_], inv[L_], fac[L_];
#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define sz(v) int(v.size())
using namespace std;
typedef long double rl;
namespace FFT {
struct cpl { rl a, b; cpl(rl a_=0, rl b_=0) : a(a_), b(b_) {}};
cpl mul(cpl x, cpl y) { return {x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a}; }
cpl add(cpl x, cpl y) { return {x.a+y.a,x.b+y.b}; }
cpl sub(cpl x, cpl y) { return {x.a-y.a,x.b-y.b}; }
const static int N = 1<<15;
const static rl PI = acos(rl(-1));
cpl wpw[N];
void fft(vector<cpl> &a, bool inv) {
int n = sz(a);
assert(1 <= n && n <= N);
assert((n & (n-1)) == 0);
for (int i = 1, j = 0, b; i < n; i++) {
for (b = n>>1; j >= b; b >>= 1) j -= b;
j += b;
if (i < j) swap(a[i],a[j]);
}
for (int b = 2; b <= n; b <<= 1) {
rl ang = 2 * PI / b * (inv ? -1 : 1);
cpl w = {cos(ang),sin(ang)};
wpw[0] = {1,0};
FO(i,1,b/2) wpw[i] = mul(w,wpw[i-1]);
for (int i = 0; i < n; i += b) FO(j,0,b/2) {
cpl u = a[i+j], v = mul(wpw[j], a[i+j+b/2]);
a[i+j] = add(u,v);
a[i+j+b/2] = sub(u,v);
}
}
if (inv) FO(i,0,n) a[i].a /= n, a[i].b /= n;
}
vector<rl> rmul(const vector<rl> &a, const vector<rl> &b) {
int n = 1;
while (n < sz(a)+sz(b)) n <<= 1;
n <<= 1;
vector<cpl> A(n), B(n);
FO(i,0,sz(a)) A[i] = {a[i],0};
FO(i,0,sz(b)) B[i] = {b[i],0};
fft(A,false); fft(B,false);
FO(i,0,n) A[i] = mul(A[i],B[i]);
fft(A,true);
vector<rl> c(n);
FO(i,0,n) c[i] = A[i].a;
return c;
}
vector<long long> imul(const vector<int> &a, const vector<int> &b) {
vector<rl> A(a.begin(),a.end()), B(b.begin(),b.end());
vector<rl> C = rmul(A,B);
vector<long long> c(sz(C));
FO(i,0,sz(c)) c[i] = roundl(C[i]);
return c;
}
vector<int> imulmod(const vector<int> &a, const vector<int> &b, int mod=MOD) {
int B = (int)sqrt(mod);
int n = sz(a), m = sz(b);
vector<int> a0(n), a1(n), b0(m), b1(m);
FO(i,0,n) { a0[i] = a[i]%B; a1[i] = a[i]/B; }
FO(i,0,m) { b0[i] = b[i]%B; b1[i] = b[i]/B; }
vector<long long> z0 = imul(a0,b0), z1 = imul(a0,b1), Z1 = imul(a1,b0), z2 = imul(a1,b1);
FO(i,0,sz(z0)) {
z0[i] += (z1[i]+Z1[i])%mod * B;
z0[i] += z2[i]%mod * B * B;
z0[i] %= mod;
}
vector<int> r(sz(z0));
FO(i,0,sz(r)) r[i] = z0[i];
return r;
}
};
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]];
}
// precalc section
{
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];
}
}
vector<mint> tb(L+1, 0);
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<int> a(p.size()), b(q.size());
for(int i = 0; i <= L; i++) a[i] = (p[i]).val;
for(int i = 0; i <= L; i++) b[i] = (q[i]).val;
vector<int> r = FFT::imulmod(a,b); r.resize(L+1);
vector<mint> ret(L+1);
for(int i = 0; i <= L; i++) ret[i] = r[i];
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);
}
tb = multiply(coef, tb);
}
mint ans = tb[L] * fac[L] / modpow(N, L);
printf("%lld\n", ans.val);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
908 ms |
4836 KB |
Output is correct |
| 2 |
Correct |
966 ms |
4832 KB |
Output is correct |
| 3 |
Correct |
832 ms |
4804 KB |
Output is correct |
| 4 |
Correct |
934 ms |
4836 KB |
Output is correct |
| 5 |
Correct |
976 ms |
4784 KB |
Output is correct |
| 6 |
Correct |
943 ms |
4804 KB |
Output is correct |
| 7 |
Correct |
871 ms |
4812 KB |
Output is correct |
| 8 |
Correct |
992 ms |
4800 KB |
Output is correct |
| 9 |
Correct |
880 ms |
4800 KB |
Output is correct |
| 10 |
Correct |
922 ms |
4772 KB |
Output is correct |
| 11 |
Correct |
898 ms |
4792 KB |
Output is correct |
| 12 |
Correct |
819 ms |
4788 KB |
Output is correct |
| 13 |
Correct |
1018 ms |
4796 KB |
Output is correct |
| 14 |
Correct |
1004 ms |
4824 KB |
Output is correct |
| 15 |
Correct |
964 ms |
4820 KB |
Output is correct |
| 16 |
Correct |
965 ms |
4772 KB |
Output is correct |
| 17 |
Correct |
1021 ms |
4800 KB |
Output is correct |
| 18 |
Correct |
1038 ms |
4800 KB |
Output is correct |
| 19 |
Correct |
856 ms |
4828 KB |
Output is correct |
| 20 |
Correct |
1002 ms |
4804 KB |
Output is correct |
| 21 |
Correct |
683 ms |
4836 KB |
Output is correct |
| 22 |
Correct |
688 ms |
4836 KB |
Output is correct |
| 23 |
Correct |
562 ms |
4836 KB |
Output is correct |
| 24 |
Correct |
637 ms |
4836 KB |
Output is correct |
| 25 |
Correct |
727 ms |
4836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1368 ms |
4808 KB |
Output is correct |
| 2 |
Correct |
1221 ms |
4832 KB |
Output is correct |
| 3 |
Correct |
2504 ms |
4828 KB |
Output is correct |
| 4 |
Correct |
2961 ms |
4832 KB |
Output is correct |
| 5 |
Correct |
1920 ms |
4816 KB |
Output is correct |
| 6 |
Correct |
2944 ms |
4800 KB |
Output is correct |
| 7 |
Correct |
3078 ms |
4792 KB |
Output is correct |
| 8 |
Correct |
2743 ms |
4832 KB |
Output is correct |
| 9 |
Correct |
430 ms |
4800 KB |
Output is correct |
| 10 |
Correct |
1073 ms |
4816 KB |
Output is correct |
| 11 |
Correct |
980 ms |
4832 KB |
Output is correct |
| 12 |
Correct |
1305 ms |
4836 KB |
Output is correct |
| 13 |
Correct |
1555 ms |
4812 KB |
Output is correct |
| 14 |
Correct |
1349 ms |
4832 KB |
Output is correct |
| 15 |
Correct |
1758 ms |
4820 KB |
Output is correct |
| 16 |
Correct |
1083 ms |
4832 KB |
Output is correct |
| 17 |
Correct |
926 ms |
4836 KB |
Output is correct |
| 18 |
Correct |
2964 ms |
4844 KB |
Output is correct |
| 19 |
Correct |
2930 ms |
4840 KB |
Output is correct |
| 20 |
Correct |
3373 ms |
4836 KB |
Output is correct |
