oj.uz

Submission #19015

# Submission time Handle Problem Language Result Execution time Memory
19015 2016-02-17T04:15:39 Z tncks0121 카드 (kriii4_Z) C++14
13 / 100
 2000 ms 4836 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

# Verdict Execution time Memory Grader output
1 Correct 918 ms 4836 KB Output is correct
2 Correct 939 ms 4832 KB Output is correct
3 Correct 837 ms 4804 KB Output is correct
4 Correct 932 ms 4836 KB Output is correct
5 Correct 930 ms 4784 KB Output is correct
6 Correct 945 ms 4804 KB Output is correct
7 Correct 917 ms 4812 KB Output is correct
8 Correct 980 ms 4800 KB Output is correct
9 Correct 884 ms 4800 KB Output is correct
10 Correct 925 ms 4772 KB Output is correct
11 Correct 901 ms 4792 KB Output is correct
12 Correct 776 ms 4788 KB Output is correct
13 Correct 1044 ms 4796 KB Output is correct
14 Correct 1060 ms 4824 KB Output is correct
15 Correct 946 ms 4820 KB Output is correct
16 Correct 998 ms 4772 KB Output is correct
17 Correct 1040 ms 4800 KB Output is correct
18 Correct 1056 ms 4800 KB Output is correct
19 Correct 876 ms 4828 KB Output is correct
20 Correct 1042 ms 4804 KB Output is correct
21 Correct 657 ms 4836 KB Output is correct
22 Correct 687 ms 4836 KB Output is correct
23 Correct 542 ms 4836 KB Output is correct
24 Correct 659 ms 4836 KB Output is correct
25 Correct 706 ms 4836 KB Output is correct

Subtask #2
0.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1362 ms 4808 KB Output is correct
2 Correct 1249 ms 4832 KB Output is correct
3 Execution timed out 2000 ms 4828 KB Program timed out
4 Halted 0 ms 0 KB -