#401796 (Java21) No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│

提出ソース

結果

問題	No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
ユーザー	37zigen
提出日時	2019-11-29 00:17:50
言語	Java21 (openjdk 21)
結果	TLE
実行時間	-
コード長	5,568 bytes
コンパイル時間	2,502 ms
コンパイル使用メモリ	80,768 KB
実行使用メモリ	225,472 KB
最終ジャッジ日時	2023-08-18 22:58:59
合計ジャッジ時間	31,814 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	640 ms 153,208 KB
testcase_01	AC	643 ms 153,040 KB
testcase_02	AC	644 ms 152,700 KB
testcase_03	TLE	-
testcase_04	AC	635 ms 154,988 KB
testcase_05	AC	2,042 ms 219,204 KB
testcase_06	AC	1,270 ms 192,700 KB
testcase_07	AC	1,273 ms 192,752 KB
testcase_08	AC	972 ms 192,084 KB
testcase_09	AC	1,373 ms 192,464 KB
testcase_10	AC	1,251 ms 192,676 KB
testcase_11	AC	936 ms 192,276 KB
testcase_12	AC	2,072 ms 221,528 KB
testcase_13	AC	1,407 ms 194,788 KB
testcase_14	AC	811 ms 159,188 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	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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) {
		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;
		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 + mod0) % 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;
		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));
	}

}

yukicoder

結果

テストケース

ソースコード