| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19018 |
2016-02-17T04:33:57 Z |
tncks0121 |
카드 (kriii4_Z) |
C++14 |
|
6 ms |
2424 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 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, max0 = 4096, 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
