Submission #19019

#	Time	Username	Problem	Language	Result	Execution time	Memory
19019		tncks0121	카드 (kriii4_Z)	C++14	100 / 100	181 ms	5708 KiB

Z

#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 L;
 
const int N_ = 3050, L_ = 3050;
 
int D[N_];
int freq[N_];
 
mint invfac[L_], inv[L_], fac[L_];

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxk = 3050*2, max0 = 1<<15, max1 = 30;


inline int fpm(LL b, int e, int m)
{
	b %= m;
	LL t = 1;
	for ( ; e; e >>= 1, (b *= b) %= m)
		if (e & 1) (t *= b) %= m;
	return t;
}

int ans;
int MXN;

struct comp
{
	double x, y;

	comp(): x(0), y(0) { }
	comp(const double &_x, const double &_y): x(_x), y(_y) { }

};

inline comp operator+(const comp &a, const comp &b) { return comp(a.x + b.x, a.y + b.y); }
inline comp operator-(const comp &a, const comp &b) { return comp(a.x - b.x, a.y - b.y); }
inline comp operator*(const comp &a, const comp &b) { return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
inline comp conj(const comp &a) { return comp(a.x, -a.y); }

const double PI = acos(-1);

comp w[max0 + 5];
int bitrev[max0 + 5];

int LLLL;

void fft(comp *a, const int &n)
{
	REP(i, 0, n) if (i < bitrev[i]) swap(a[i], a[bitrev[i]]);
	for (int i = 2, lyc = n >> 1; i <= n; i <<= 1, lyc >>= 1)
		for (int j = 0; j < n; j += i)
		{
			comp *l = a + j, *r = a + j + (i >> 1), *p = w;
			REP(k, 0, i >> 1)
			{
				comp tmp = *r * *p;
				*r = *l - tmp, *l = *l + tmp;
				++l, ++r, p += lyc;
			}
		}
}

inline void fft_prepare()
{
	REP(i, 0, MXN) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (LLLL - 1));
	REP(i, 0, MXN) w[i] = comp(cos(2 * PI * i / MXN), sin(2 * PI * i / MXN));
}

inline void conv(int *x, int *y, int *z)
{
	REP(i, 0, L + 1) (x[i] += Mod) %= Mod, (y[i] += Mod) %= Mod;
	static comp a[max0 + 5], b[max0 + 5];
	static comp dfta[max0 + 5], dftb[max0 + 5], dftc[max0 + 5], dftd[max0 + 5];

	REP(i, 0, L + 1) a[i] = comp(x[i] & 32767, x[i] >> 15);
	REP(i, 0, L + 1) b[i] = comp(y[i] & 32767, y[i] >> 15);
	REP(i, L + 1, MXN) a[i] = b[i] = comp(0, 0);
	fft(a, MXN), fft(b, MXN);
	REP(i, 0, MXN)
	{
		int j = (MXN - i) & (MXN - 1);
		static comp da, db, dc, dd;
		da = (a[i] + conj(a[j])) * comp(0.5, 0);
		db = (a[i] - conj(a[j])) * comp(0, -0.5);
		dc = (b[i] + conj(b[j])) * comp(0.5, 0);
		dd = (b[i] - conj(b[j])) * comp(0, -0.5);
		dfta[j] = da * dc;
		dftb[j] = da * dd;
		dftc[j] = db * dc;
		dftd[j] = db * dd;
	}
	REP(i, 0, MXN) a[i] = dfta[i] + dftb[i] * comp(0, 1);
	REP(i, 0, MXN) b[i] = dftc[i] + dftd[i] * comp(0, 1);
	fft(a, MXN), fft(b, MXN);
	REP(i, 0, L + 1)
	{
		int da = (LL)(a[i].x / MXN + 0.5) % Mod;
		int db = (LL)(a[i].y / MXN + 0.5) % Mod;
		int dc = (LL)(b[i].x / MXN + 0.5) % Mod;
		int dd = (LL)(b[i].y / MXN + 0.5) % Mod;
		z[i] = (da + ((LL)(db + dc) << 15) + ((LL)dd << 30)) % Mod;
	}
}

static int tmp[maxk + 5], a[maxk + 5], b[maxk + 5];


int main() {
	int N;
    assert(scanf("%d%d", &N, &L) == 2);
	MXN = (L + 1) << 1;
	LLLL = 0;
	while ((1 << LLLL) < MXN) ++LLLL;
	MXN = 1 << LLLL;
	fft_prepare();

    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) {
        	for(int i = 0; i <= L; i++) a[i] = p[i].val, b[i] = q[i].val;
        	conv(a, b, tmp);
        	vector<mint> ret(L+1);
        	for(int i = 0; i <= L; i++) ret[i] = tmp[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 / 13
• Subtask 2: 87 / 87