結果

問題 No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
ユーザー CuriousFairy315CuriousFairy315
提出日時 2019-12-01 19:46:46
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 6,533 bytes
コンパイル時間 4,194 ms
コンパイル使用メモリ 76,384 KB
実行使用メモリ 165,892 KB
最終ジャッジ日時 2023-08-18 23:15:01
合計ジャッジ時間 20,161 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 289 ms
130,248 KB
testcase_01 AC 277 ms
132,204 KB
testcase_02 AC 281 ms
130,172 KB
testcase_03 AC 329 ms
132,172 KB
testcase_04 AC 277 ms
130,048 KB
testcase_05 AC 326 ms
132,208 KB
testcase_06 AC 302 ms
129,916 KB
testcase_07 AC 295 ms
130,172 KB
testcase_08 AC 304 ms
132,124 KB
testcase_09 AC 305 ms
130,204 KB
testcase_10 AC 304 ms
130,156 KB
testcase_11 AC 306 ms
130,292 KB
testcase_12 AC 319 ms
131,964 KB
testcase_13 AC 307 ms
130,036 KB
testcase_14 AC 297 ms
130,164 KB
testcase_15 AC 1,098 ms
165,600 KB
testcase_16 AC 2,197 ms
165,892 KB
testcase_17 TLE -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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));
	}

}
0