結果
問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│ |
ユーザー | 37zigen |
提出日時 | 2019-12-01 22:22:35 |
言語 | Java19 (openjdk 21) |
結果 |
AC
|
実行時間 | 2,303 ms / 5,000 ms |
コード長 | 5,560 bytes |
コンパイル時間 | 3,617 ms |
コンパイル使用メモリ | 78,316 KB |
実行使用メモリ | 158,528 KB |
最終ジャッジ日時 | 2023-08-18 23:08:07 |
合計ジャッジ時間 | 25,515 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge10 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 357 ms
120,176 KB |
testcase_01 | AC | 341 ms
119,988 KB |
testcase_02 | AC | 355 ms
119,768 KB |
testcase_03 | AC | 380 ms
120,168 KB |
testcase_04 | AC | 355 ms
119,960 KB |
testcase_05 | AC | 375 ms
120,148 KB |
testcase_06 | AC | 362 ms
120,340 KB |
testcase_07 | AC | 376 ms
119,792 KB |
testcase_08 | AC | 349 ms
119,952 KB |
testcase_09 | AC | 377 ms
120,140 KB |
testcase_10 | AC | 357 ms
120,112 KB |
testcase_11 | AC | 347 ms
119,880 KB |
testcase_12 | AC | 418 ms
120,540 KB |
testcase_13 | AC | 384 ms
120,068 KB |
testcase_14 | AC | 351 ms
119,860 KB |
testcase_15 | AC | 915 ms
149,892 KB |
testcase_16 | AC | 2,303 ms
156,824 KB |
testcase_17 | AC | 365 ms
120,176 KB |
testcase_18 | AC | 380 ms
120,260 KB |
testcase_19 | AC | 367 ms
119,964 KB |
testcase_20 | AC | 378 ms
120,408 KB |
testcase_21 | AC | 373 ms
120,192 KB |
testcase_22 | AC | 1,362 ms
151,740 KB |
testcase_23 | AC | 2,292 ms
155,708 KB |
testcase_24 | AC | 1,400 ms
151,700 KB |
testcase_25 | AC | 2,296 ms
157,712 KB |
testcase_26 | AC | 2,303 ms
158,528 KB |
ソースコード
import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } int MAX = 2123456; 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) { return fac[n] * ifac[k] % mod * ifac[n - k] % mod; } long solve(int X, int Y, int Z, long mod0) { if (X == 0 && Y == 0 && Z == 0) return 1; int[] xxx = new int[] { X, Y, Z }; Arrays.sort(xxx); X = xxx[2]; Y = xxx[1]; Z = xxx[0]; long[] f = new long[Math.min(X + Y, Math.min(Y + Z, Z + X)) + 1]; long[] g = new long[Math.min(X, Y) + 1]; long[] h = new long[Z + 1]; for (int i = 0; i < f.length; ++i) { f[i] = pw2[X + Y + Z - 1 - i] * (i % 2 == 0 ? 1 : (mod0 - 1)) % mod0 * fac[X + Y + Z - i] % mod0 * ifac[X + Y - i] % mod0; } for (int i = 0; i < g.length; ++i) { g[Math.min(X, Y) - i] = fac[X + Y - i] * ifac[X - i] % mod0 * ifac[Y - i] % mod0 * ifac[i] % mod0; } for (int i = 0; i < h.length; ++i) { h[Z - i] = ifac[Z - i] * ifac[i] % mod0; } long[] fg = mul(f, g, Math.min(X, Y) + Z + 1, mod0); long ret = 0; for (int i = Math.max(0, Math.min(X, Y) + Z - h.length + 1); i < Math.min(fg.length, Math.min(X, Y) + Z + 1); ++i) { ret = (ret + fg[i] * h[Math.min(X, Y) + Z - i] % mod0) % mod0; } return ret; } long[] mul(long[] a, long[] b, int len, 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]); } long[] ret = c[0]; long mod1 = MOD[0], mod2 = MOD[1], mod3 = MOD[2]; long gamma2 = inv(mod1, mod2), gamma3 = inv(mod1 * mod2 % mod3, mod3); for (int i = 0; i < ret.length; ++i) { ret[i] = garner(c[0][i], c[1][i], c[2][i], mod1, mod2, mod3, gamma2, gamma3, 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 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; } long garner(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; } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }