#204602 (Java21) No.569 3 x N グリッドのパスの数

提出ソース

結果

問題	No.569 3 x N グリッドのパスの数
ユーザー	37zigen
提出日時	2017-09-14 00:36:11
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	7,169 bytes
コンパイル時間	3,513 ms
コンパイル使用メモリ	80,556 KB
実行使用メモリ	45,140 KB
最終ジャッジ日時	2024-11-07 20:09:34
合計ジャッジ時間	15,342 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	130 ms 41,140 KB
testcase_01	AC	131 ms 41,272 KB
testcase_02	AC	120 ms 40,900 KB
testcase_03	AC	129 ms 41,104 KB
testcase_04	AC	130 ms 41,416 KB
testcase_05	AC	128 ms 41,468 KB
testcase_06	AC	130 ms 41,236 KB
testcase_07	AC	131 ms 41,440 KB
testcase_08	AC	132 ms 41,420 KB
testcase_09	AC	134 ms 41,172 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	RE	-
testcase_41	RE	-
testcase_42	RE	-
testcase_43	RE	-
testcase_44	RE	-
testcase_45	RE	-
testcase_46	RE	-
testcase_47	RE	-
testcase_48	RE	-
testcase_49	RE	-
testcase_50	RE	-
testcase_51	RE	-
testcase_52	RE	-
testcase_53	RE	-
testcase_54	RE	-
testcase_55	RE	-
testcase_56	RE	-
testcase_57	RE	-
testcase_58	RE	-
testcase_59	RE	-

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

ソースコード

raw source code

import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		new Main().run();
	}

	// 任意剰余が取れるようにする。

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		++n;
		// long[] coe = new long[K + 1];
		// Arrays.fill(coe, -1);
		// coe[K] = 1;
		long[] seq = new long[] { 1, 8, 38, 184, 976, 5382, 29739, 163496, 896476, 4913258, 26932712, 147657866 };
		long[] coe = new long[] { 1, 8, 38, 184, 976, 5382, 29739, 163496, 896476, 4913258, 26932712, 147657866 };
		long MODULO = 1_000_000_000 + 7;
		System.out.println(nthMod(seq, coe, n, MODULO));
	}

	long[] NTTMODULO = new long[] { 1012924417L, 1004535809L, 975175681L };
	long[] NTTROOT = new long[] { 5, 3, 17 };

	long nthMod(long[] seq, long[] coe, long n, long MODULO) {
		--n;
		long[] ans = new long[3];
		for (int i = 0; i < 3; ++i) {
			Poly ret = new Poly(NTTMODULO[i], NTTROOT[i], 1);
			Poly x = new Poly(NTTMODULO[i], NTTROOT[i], 0, 1);// x^n
			Poly mod = new Poly(NTTMODULO[i], NTTROOT[i], seq);
			long n_ = n;
			for (; n_ > 0; n_ >>= 1) {
				if (n_ % 2 == 1) {
					ret.mulFFT(x);
					ret.mod(mod);
				}
				x.mulFFT(x);
				x.mod(mod);
			}
			for (int j = 0; j < ret.intLen; ++j) {
				ans[i] += ret.val[j] * (coe[j] % NTTMODULO[i]) % NTTMODULO[i];
				if (ans[i] >= NTTMODULO[i])
					ans[i] -= NTTMODULO[i];
			}
		}
		long ret = 0;
		long mul = 1;
		for (int i = 0; i < 3; ++i) {
			long inv = 1;
			for (int j = 0; j < i; ++j) {
				inv = inv * inv(NTTMODULO[j], NTTMODULO[i]) % MODULO;
			}
			inv = inv * (ans[i] - ret) % MODULO;
			if (inv < 0)
				inv += MODULO;
			ret = (ret + inv * mul) % MODULO;
			mul = mul * NTTMODULO[i] % MODULO;
		}
		return ret;
	}

	public static long inv(long a, long mod) {
		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;
		}
		return p < 0 ? p + mod : p;
	}

	long pow(long a, long n, long MODULO) {
		long ret = 1;
		for (; n > 0; n >>= 1, a = a * a % MODULO) {
			if (n % 2 == 1)
				ret = ret * a % MODULO;
		}
		return ret;
	}

	class Poly {
		long[] val;
		long MODULO;
		long root;
		int intLen = 0;

		public Poly(long MODULO_, long root_, long... vs) {
			val = vs;
			intLen = val.length;
			MODULO = MODULO_;
			root = root_;
		}

		void add(Poly a) {
			if (val.length < a.intLen) {
				val = Arrays.copyOf(val, a.val.length);
			}
			for (int i = 0; i < a.intLen; ++i) {
				val[i] += a.val[i];
				if (val[i] >= MODULO)
					val[i] -= MODULO;
			}
			intLen = 0;
			for (int i = 0; i < val.length; ++i) {
				if (i + 1 > intLen && val[i] != 0)
					intLen = i + 1;
			}
		}

		void sub(Poly a) {
			if (a.intLen > val.length) {
				val = Arrays.copyOf(val, a.intLen);
			}
			for (int i = 0; i < a.intLen; ++i) {
				val[i] -= a.val[i];
				if (val[i] < 0)
					val[i] += MODULO;
			}
			intLen = 0;
			for (int i = 0; i < val.length; ++i) {
				if (val[i] != 0 && intLen < i + 1)
					intLen = i + 1;
			}
		}

		void mulFFT(Poly a) {
			if (a.intLen == 0 || intLen == 0) {
				intLen = 0;
				val = new long[] { 0 };
				return;
			}
			val = mul(val, a.val);
			intLen = (intLen - 1) + (a.intLen - 1) + 1;
			return;
		}

		// Newton method
		// Karatsuba:n^1.58
		// FFT:nlgn
		void div(Poly b) {
			b.monic();
			if (b.intLen == 0)
				throw new ArithmeticException();
			if (b.intLen > intLen) {
				val = new long[] { 0 };
				intLen = 0;
				return;
			}
			int n = intLen - 1;
			int m = b.intLen - 1;
			b.rev(m + 1);
			Poly a = new Poly(MODULO, root, 1);
			for (int t = 1; t < n - m + 1; t *= 2) {
				Poly tmp = a.copy();
				tmp.mulFFT(a);
				tmp.mulFFT(b);
				a.mulFFT(new Poly(MODULO, root, 2));
				a.sub(tmp);
				if (a.intLen > n - m + 1) {
					a.intLen = n - m + 1;
					a.val = Arrays.copyOf(a.val, a.intLen);
				}
			}
			rev(n + 1);
			mulFFT(a);
			rev(n - m + 1);
			if (intLen - 1 > n - m) {
				intLen = n - m + 1;
				val = Arrays.copyOf(val, intLen);
			}
			b.rev(m + 1);
			return;
		}

		void mod(Poly mod) {
			Poly tmp = copy();
			tmp.div(mod);
			tmp.mulFFT(mod);
			sub(tmp);
			val = Arrays.copyOf(val, intLen);
		}

		int compare(Poly a) {
			if (intLen != a.intLen) {
				return Integer.compare(intLen, a.intLen);
			}
			for (int i = intLen - 1; i >= 0; --i) {
				if (val[i] == a.val[i])
					continue;
				return Double.compare(val[i], a.val[i]);
			}
			return 0;
		}

		void shift(int k) {
			if (intLen == 0)
				return;
			if (intLen + k <= 0) {
				val = new long[] { 0 };
				intLen = 0;
				return;
			}
			Poly u = copy();
			val = new long[intLen + k];
			if (k >= 0)
				System.arraycopy(u.val, 0, val, k, intLen);
			else
				System.arraycopy(u.val, -k, val, 0, intLen + k);
			intLen += k;
		}

		void monic() {
			if (intLen == 0)
				return;
			long v = inv(val[intLen - 1], MODULO);
			for (int i = 0; i < intLen; ++i) {
				val[i] *= v;
				val[i] %= MODULO;
			}
		}

		void rev(int Len) {
			if (intLen < Len)
				val = Arrays.copyOf(val, Len);
			int s = 0;
			int t = Len;
			while (t - s > 0) {
				long d = val[s];
				val[s] = val[t - 1];
				val[t - 1] = d;
				++s;
				--t;
			}
			intLen = 0;
			for (int i = val.length - 1; i >= 0; --i) {
				if (val[i] != 0) {
					intLen = i + 1;
					break;
				}
			}
		}

		Poly copy() {
			Poly ret = new Poly(MODULO, root, 0);
			ret.val = Arrays.copyOf(val, val.length);
			ret.intLen = intLen;
			return ret;

		}

		long[] mul(long[] a, long[] b) {
			int n = Integer.highestOneBit(a.length + b.length) << 1;
			a = Arrays.copyOf(a, n);
			b = Arrays.copyOf(b, n);
			a = fft(a, false);
			b = fft(b, false);
			long ninv = pow(n, MODULO - 2);
			for (int i = 0; i < n; ++i) {
				a[i] = a[i] * b[i] % MODULO;
			}
			a = fft(a, true);
			for (int i = 0; i < n; ++i)
				a[i] = a[i] * ninv % MODULO;
			return a;
		}

		long[] fft(long[] a, boolean inv) {
			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[c];
					a[c] = a[i];
					a[i] = d;
				}
			}

			for (int i = 1; i < n; i <<= 1) {
				long w = pow(root, (MODULO - 1) / (2 * i));
				if (inv)
					w = pow(w, MODULO - 2);
				for (int j = 0; j < n; j += 2 * i) {
					long wn = 1;
					for (int k = 0; k < i; ++k) {
						long u = a[k + j];
						long v = a[k + j + i] * wn % MODULO;
						a[k + j] = (u + v) % MODULO;
						a[k + j + i] = (u - v + MODULO) % MODULO;
						wn = wn * w % MODULO;
					}
				}
			}
			return a;
		}

		long pow(long a, long n) {
			long ret = 1;
			for (; n > 0; n >>= 1, a = a * a % MODULO) {
				if (n % 2 == 1)
					ret = ret * a % MODULO;
			}
			return ret;
		}

		void check() {
			for (int i = val.length - 1; i >= 0; --i) {
				if (val[i] != 0 && i + 1 > intLen) {
					throw new AssertionError();
				}
			}
		}
	}

	long gcd(long a, long b) {
		if (a > b) {
			return gcd(b, a);
		}
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}

yukicoder

結果

テストケース

ソースコード