oj.uz

답안 #19016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19016 2016-02-17T04:16:39 Z tncks0121 카드 (kriii4_Z) C++14
100 / 100
 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;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
87.0 / 87.0

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