結果
問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│ |
ユーザー | 37zigen |
提出日時 | 2019-11-29 00:08:41 |
言語 | Java19 (openjdk 21) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,607 bytes |
コンパイル時間 | 2,979 ms |
コンパイル使用メモリ | 78,668 KB |
実行使用メモリ | 254,328 KB |
最終ジャッジ日時 | 2023-08-18 22:56:46 |
合計ジャッジ時間 | 34,231 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 769 ms
153,072 KB |
testcase_01 | AC | 750 ms
152,660 KB |
testcase_02 | AC | 709 ms
152,840 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 732 ms
153,212 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 1,418 ms
192,584 KB |
testcase_10 | AC | 1,347 ms
192,956 KB |
testcase_11 | AC | 1,021 ms
192,272 KB |
testcase_12 | AC | 2,179 ms
221,036 KB |
testcase_13 | WA | - |
testcase_14 | AC | 843 ms
158,920 KB |
testcase_15 | TLE | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
ソースコード
import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } int MAX = 3123456; long[] fac = new long[MAX]; long[] ifac = new long[MAX]; long[] inv = new long[MAX]; long[] pw2 = new long[MAX]; { long MOD = (long) 1e9 + 7; fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = pw2[0] = 1; pw2[1] = 2; 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; pw2[i] = 2 * pw2[i - 1] % MOD; } } void run() { 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, (long) 1e9 + 7)); } long comb(int n, int k, long mod) { if (n >= k) return fac[n] * ifac[k] % mod * ifac[n - k] % mod; else return 0; } long solve(int X, int Y, int Z, long mod0) { if (X == 0 && Y == 0 && Z == 0) return 1; long[] f = new long[X + Y + Z + 2]; long[] g = new long[X + Y + Z + 2]; long[] q = new long[X + Y + Z + 2]; long[] h = new long[X + Y + Z + 2]; for (int i = 1; i < q.length; ++i) { q[i] = ifac[i]; } int M = (int) Math.sqrt(X + Y + Z); for (int i = 0; i <= X + Y + Z; ++i) { long sub = h[i]; for (int j = 1; j < Math.min(i, (i % M == 0 ? M : i % M)); ++j) { sub = (sub + g[i - j] * q[j] % mod0) % mod0; } f[i] = comb(X + i, i, mod0) * comb(Y + i, i, mod0) % mod0 * comb(Z + i, i, mod0) % mod0 - fac[i + 1] * sub % mod0; g[i] = f[i] * q[i + 1] % mod0; if (i % M == 0) h = mul(g, q, mod0); } long ret = 0; for (int i = 0; i <= X + Y + Z; ++i) ret = (ret + f[i]) % mod0; ret = (ret + mod0) % mod0; return ret; } long[] mul(long[] a, long[] b, long mod0) { if (a.length == 1) { long[] ret = new long[b.length]; for (int i = 0; i < b.length; ++i) { ret[i] = a[0] * b[i] % mod0; } return ret; } else if (b.length == 1) { long[] ret = new long[a.length]; for (int i = 0; i < a.length; ++i) { ret[i] = a[i] * b[0] % mod0; } return ret; } // 2^25*5+1, 2^24*73+1, 2^26*7+1 long[] MOD = new long[] { 167772161, 1224736769, 469762049 }; long[] gen = new long[] { 3, 3, 3 }; long[][] c = new long[3][]; for (int i = 0; i < 3; ++i) { c[i] = mul(Arrays.copyOf(a, a.length), Arrays.copyOf(b, b.length), MOD[i], gen[i]); } for (int i = 0; i < c[0].length; ++i) { c[0][i] = garner(new long[] { c[0][i], c[1][i], c[2][i] }, MOD, mod0); } return c[0]; } long[] mul(long[] a, long[] b, long mod, long gen) { int degree = Math.max(a.length - 1, b.length - 1); int level = Long.numberOfTrailingZeros(mod - 1); long root = gen; long omega = pow(root, (mod - 1) >> level, mod); int n = Integer.highestOneBit(2 * degree) << 1; 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 < n; ++i) a[i] = a[i] * b[i] % mod; a = fft(a, true, mod, roots, iroots); long inv = inv(n, mod); for (int i = 0; i < n; ++i) { a[i] = a[i] * inv % mod; } return a; } long[] fft(long[] a, boolean inv, long mod, long[] roots, long[] iroots) { int n = a.length; int c = 0; for (int i = 1; i < n; ++i) { for (int j = n >> 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 < n; i *= 2) { long w; if (!inv) w = roots[level - Integer.numberOfTrailingZeros(i) - 1]; else w = iroots[level - Integer.numberOfTrailingZeros(i) - 1]; for (int j = 0; j < n; j += 2 * i) { long wn = 1; for (int k = 0; k < i; ++k) { long u = a[j + k]; long v = a[j + k + i] * wn % mod; a[j + k] = u + v; a[j + k + i] = u - v; if (a[j + k] >= mod) a[j + k] -= mod; if (a[j + k + i] < 0) a[j + k + i] += mod; wn = wn * w % mod; } } } return a; } long inv(long a, long mod) { a %= mod; if (a < 0) a += mod; if (a == 0) { throw new AssertionError(); // return 1; } long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } long ret = p < 0 ? (p + mod) : p; return ret; } 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 < n; i++) { long prod = 1; for (int j = 0; j < i; j++) { prod = prod * mod[j] % mod[i]; } gamma[i] = inv(prod, mod[i]); } long[] v = new long[n]; v[0] = x[0]; for (int i = 1; i < n; 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]; while (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; } long pow(long a, long n, long mod) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % mod) { if (n % 2 == 1) ret = ret * a % mod; } return ret; } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }