結果
| 問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д＜│ |
| コンテスト | |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2019-12-01 19:46:46 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,533 bytes |
| 記録 | |
| コンパイル時間 | 3,879 ms |
| コンパイル使用メモリ | 89,844 KB |
| 実行使用メモリ | 360,072 KB |
| 最終ジャッジ日時 | 2024-11-28 10:03:24 |
| 合計ジャッジ時間 | 72,301 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 14 TLE * 8 |
ソースコード
package yukicoder_3679;
import java.util.Arrays;
import java.util.Scanner;
class Main2 {
public static void main(String[] args) {
new Main2().run();
}
static final int MAX = 3123456;
static final long[] fac = new long[MAX];
static final long[] ifac = new long[MAX];
static final long[] inv = new long[MAX];
static final long MOD = 1_000_000_007;
{
fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1;
for (int i = 2; i < fac.length; ++i) {
fac[i] = i * fac[i - 1] % MOD;
inv[i] = MOD - inv[(int)(MOD % i)] * (MOD / i) % MOD;
ifac[i] = inv[i] * ifac[i - 1] % MOD;
}
}
void run() {
try (Scanner sc = new Scanner(System.in);) {
int X = sc.nextInt();
int Y = sc.nextInt();
int Z = sc.nextInt();
System.out.println(solve(X, Y, Z, MOD));
}
}
static final long comb(int n, int k, long mod) {
return fac[n] * ifac[k] % mod * ifac[n - k] % mod;
}
static final long solve(int X, int Y, int Z, long mod0) {
if (X == 0 && Y == 0 && Z == 0) return 1;
long[] p = new long[X + Y + Z + 2];
long[] q = new long[X + Y + Z + 2];
for (int i = 0; i < p.length; ++i) {
p[i] = ifac[i + 1] * comb(X + i, i, mod0) % mod0 * comb(Y + i, i, mod0) % mod0 * comb(Z + i, i, mod0) % mod0;
}
for (int i = 0;i < q.length;++ i) q[i] = (i & 1) == 0 ? ifac[i] : mod0 - ifac[i];
long[] h = mul(p, q, mod0);
long ret = 0;
for (int i = 0; i < X + Y + Z; ++i) ret = (ret + fac[i + 1] * h[i]) % mod0;
return ret;
}
static final long[] inv(long[] F, long mod0) {
long[] G = new long[1];
G[0] = 1;
while (G.length < F.length) {
int len = G.length;
G = subtract(mul(G, 2, mod0), mul(Arrays.copyOf(F, 2 * len), mul(G, G, mod0), mod0), mod0);
G = Arrays.copyOf(G, 2 * len);
}
return G;
}
static final long[] mul(long[] a, long coe, long mod0) {
long[] ret = Arrays.copyOf(a, a.length);
for (int i = 0; i < ret.length; ++i) {
ret[i] *= coe;
ret[i] %= mod0;
}
return ret;
}
static final long[] subtract(long[] a, long[] b, long mod0) {
long[] ret = new long[Math.max(a.length, b.length)];
int l = Math.min(a.length, b.length);
for (int i = 0; i < l; ++i) {
ret[i] = (a[i] - b[i] + mod0) % mod0;
}
if (a.length > b.length) {
for (int i = l; i < ret.length; ++i)
ret[i] = a[i];
} else {
for (int i = l; i < ret.length; ++i)
ret[i] = mod0 - b[i];
}
return ret;
}
static final long[] mul(long[] a, long[] b, long mod0) {
if (a.length == 1) {
return mul(b, a[0], mod0);
} else if (b.length == 1) { return mul(a, b[0], mod0); }
// 2^25*5+1, 2^24*73+1, 2^26*7+1
long[] MOD = new long[]{167772161, 469762049, 1224736769}; // 昇順
long[] gen = new long[]{3, 3, 3};
long[][] c = new long[3][];
{
for (int i = 0; i < 3; ++i) {
c[i] = mul(a, b, MOD[i], gen[i]);
}
}
long mod1 = MOD[0], mod2 = MOD[1], mod3 = MOD[2];
long gamma2 = inv(mod1, mod2), gamma3 = inv(mod1 * mod2 % mod3, mod3);
long[] ret = c[0];
for (int i = 0; i < ret.length; ++i) {
//c[0][i] = garner(new long[]{c[0][i], c[1][i], c[2][i]}, MOD, mod0);
ret[i] = garner3(c[0][i], c[1][i], c[2][i], mod1, mod2, mod3, gamma2, gamma3, mod0);
}
return c[0];
}
static final long[] mul(long[] a, long[] b, long mod, long gen) {
int degree = Math.max(a.length - 1, b.length - 1);
int n = Integer.highestOneBit(2 * degree) << 1;
int level = Long.numberOfTrailingZeros(mod - 1);
long root = gen;
long omega = pow(root, (mod - 1) >> level, mod);
long[] roots = new long[level];
long[] iroots = new long[level];
roots[0] = omega;
iroots[0] = inv(omega, mod);
for (int i = 1; i < level; ++i) {
roots[i] = roots[i - 1] * roots[i - 1] % mod;
iroots[i] = iroots[i - 1] * iroots[i - 1] % mod;
}
a = Arrays.copyOf(a, n);
b = Arrays.copyOf(b, n);
a = fft(a, false, mod, roots, iroots);
b = fft(b, false, mod, roots, iroots);
for (int i = 0; i < a.length; ++i) {
a[i] *= b[i];
a[i] %= mod;
}
a = fft(a, true, mod, roots, iroots);
long inv = inv(a.length, mod);
for (int i = 0; i < a.length; ++i) {
a[i] *= inv;
a[i] %= mod;
}
return a;
}
static final long[] fft(long[] a, boolean inv, long mod, long[] roots, long[] iroots) {
for (int i = 1, c = 0; i < a.length; ++i) {
for (int j = a.length >> 1; j > (c ^= j); j >>= 1);
if (c > i) {
long d = a[i];
a[i] = a[c];
a[c] = d;
}
}
int level = Long.numberOfTrailingZeros(mod - 1);
for (int i = 1; i < a.length; i <<= 1) {
int root = level - Integer.numberOfTrailingZeros(i) - 1;
long w = inv ? iroots[root] : roots[root];
for (int j = 0; j < a.length; j += i << 1) {
long wn = 1;
for (int k = j, l = i + j; k < l; ++k) {
long u = a[k], v = a[k + i] * wn % mod, sum = u + v, diff = u - v;
a[k + i] = diff < 0 ? diff += mod : diff;
a[k] = sum >= mod ? sum -= mod : sum;
wn *= w;
wn %= mod;
}
}
}
return a;
}
static final long inv(long a, long mod) {
long b = mod;
long p = 1, q = 0, c, d;
do {
c = a / b;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
} while (b > 0);
long ret = p < 0 ? (p + mod) : p;
return ret;
}
static final long garner3(long x1, long x2, long x3, long mod1, long mod2, long mod3, long gamma2, long gamma3, long mod0) {
long v1, v2, v3;
v1 = x1;
v2 = (x2 - v1 + mod2) * gamma2 % mod2;
v3 = (x3 - (v2 * mod1 + v1) % mod3 + mod3) * gamma3 % mod3;
long ret = v3;
ret = (ret * mod2 + v2) % mod0;
ret = (ret * mod1 + v1) % mod0;
return ret;
}
/*static final long garner(long[] x, long[] mod, long mod0) {
assert x.length == mod.length;
int n = x.length;
long[] gamma = new long[n];
for (int i = 0; i < gamma.length; i++ ) {
long prod = 1;
for (int j = 0; j < i; j++ ) {
prod *= mod[j];
prod %= mod[i];
}
gamma[i] = inv(prod, mod[i]);
}
long[] v = new long[n];
v[0] = x[0];
for (int i = 1; i < v.length; i++ ) {
long tmp = v[i - 1];
for (int j = i - 2; j >= 0; j-- ) {
tmp = (tmp * mod[j] + v[j]) % mod[i];
}
v[i] = (x[i] - tmp) * gamma[i] % mod[i];
if (v[i] < 0) v[i] += mod[i];
}
long ret = 0;
for (int i = v.length - 1; i >= 0; i-- ) {
ret = (ret * mod[i] + v[i]) % mod0;
}
return ret;
}*/
static final long pow(long a, long n, long mod) {
long ret = 1, num = a;
while (n != 0) {
if ((n & 1) != 0) ret = ret * num % mod;
n >>>= 1;
num = num * num % mod;
}
return ret;
}
static final void tr(Object... objects) {
System.out.println(Arrays.deepToString(objects));
}
}