Submission #19014

#TimeUsernameProblemLanguageResultExecution timeMemory
19014tncks0121카드 (kriii4_Z)C++14
0 / 100
0 ms3292 KiB
#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<<13; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...