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

提出ソース

結果

問題	No.569 3 x N グリッドのパスの数
ユーザー	37zigen
提出日時	2017-09-14 04:29:11
言語	Java21 (openjdk 21)
結果	AC
実行時間	434 ms / 2,000 ms
コード長	9,045 bytes
コンパイル時間	2,243 ms
コンパイル使用メモリ	88,536 KB
実行使用メモリ	49,360 KB
最終ジャッジ日時	2024-04-25 10:33:05
合計ジャッジ時間	19,617 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	115 ms 41,292 KB
testcase_01	AC	111 ms 39,904 KB
testcase_02	AC	113 ms 40,752 KB
testcase_03	AC	120 ms 41,232 KB
testcase_04	AC	120 ms 41,424 KB
testcase_05	AC	116 ms 41,160 KB
testcase_06	AC	118 ms 41,556 KB
testcase_07	AC	118 ms 40,884 KB
testcase_08	AC	111 ms 40,440 KB
testcase_09	AC	127 ms 40,312 KB
testcase_10	AC	131 ms 41,480 KB
testcase_11	AC	117 ms 40,124 KB
testcase_12	AC	124 ms 41,204 KB
testcase_13	AC	119 ms 40,664 KB
testcase_14	AC	121 ms 41,276 KB
testcase_15	AC	125 ms 40,992 KB
testcase_16	AC	129 ms 41,484 KB
testcase_17	AC	123 ms 41,336 KB
testcase_18	AC	128 ms 41,096 KB
testcase_19	AC	125 ms 40,292 KB
testcase_20	AC	259 ms 45,520 KB
testcase_21	AC	273 ms 45,152 KB
testcase_22	AC	258 ms 44,816 KB
testcase_23	AC	268 ms 45,180 KB
testcase_24	AC	260 ms 45,452 KB
testcase_25	AC	257 ms 45,172 KB
testcase_26	AC	270 ms 45,304 KB
testcase_27	AC	253 ms 45,156 KB
testcase_28	AC	272 ms 45,524 KB
testcase_29	AC	271 ms 45,280 KB
testcase_30	AC	262 ms 44,888 KB
testcase_31	AC	283 ms 45,244 KB
testcase_32	AC	254 ms 45,332 KB
testcase_33	AC	267 ms 45,340 KB
testcase_34	AC	273 ms 45,304 KB
testcase_35	AC	275 ms 46,396 KB
testcase_36	AC	280 ms 45,296 KB
testcase_37	AC	244 ms 45,548 KB
testcase_38	AC	265 ms 45,320 KB
testcase_39	AC	269 ms 45,392 KB
testcase_40	AC	398 ms 47,804 KB
testcase_41	AC	424 ms 47,820 KB
testcase_42	AC	434 ms 47,808 KB
testcase_43	AC	406 ms 48,072 KB
testcase_44	AC	404 ms 47,856 KB
testcase_45	AC	411 ms 47,836 KB
testcase_46	AC	410 ms 47,844 KB
testcase_47	AC	393 ms 48,536 KB
testcase_48	AC	408 ms 47,752 KB
testcase_49	AC	391 ms 48,076 KB
testcase_50	AC	389 ms 48,848 KB
testcase_51	AC	392 ms 47,884 KB
testcase_52	AC	421 ms 47,764 KB
testcase_53	AC	393 ms 47,688 KB
testcase_54	AC	398 ms 48,820 KB
testcase_55	AC	380 ms 49,360 KB
testcase_56	AC	409 ms 47,752 KB
testcase_57	AC	416 ms 47,676 KB
testcase_58	AC	404 ms 48,960 KB
testcase_59	AC	395 ms 47,204 KB

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

ソースコード

raw source code

import java.io.FileNotFoundException;
import java.math.BigInteger;
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);
		long n = sc.nextLong();
		// long[] coe = new long[K + 1];
		// Arrays.fill(coe, -1);
		// coe[K] = 1;
		long[] init = new long[] { 1, 8, 38, 184, 976, 5382, 29739, 163496, 896476, 4913258, 26932712, 147657866 };
		long[] coe = new long[] { 1, 4, -12, -40, 69, 94, -175, 16, 133, -124, 54, -12, 1 };
		long MODULO = 1_000_000_000 + 7;
		System.out.println(nthMod(coe, init, n, MODULO));
	}

	long nthMod(long[] coe, long[] init, long n, long MODULO) {
		Poly ret = new Poly(MODULO, new long[] { 1 });
		Poly x = new Poly(MODULO, new long[] { 0, 1 });// x^n
		Poly mod = new Poly(MODULO, coe);
		long n_ = n;
		for (; n_ > 0; n_ >>= 1) {
			if (n_ % 2 == 1) {
				ret.mulFFT(x);
				ret.mod(mod);
			}
			x.mulFFT(x);
			x.mod(mod);

		}
		long ans = 0;
		for (int j = 0; j < ret.intLen; ++j) {
			ans += ret.val[j] * init[j] % MODULO;
			ans %= MODULO;
		}
		return ans;
	}

	long garner(long[] x, long[] mod, long MOD) {
		int n = x.length;
		long[] gamma = new long[n];
		for (int i = 0; i < n; ++i) {
			long prd = 1;
			for (int j = 0; j < i; ++j) {
				prd = prd * mod[j] % mod[i];
			}
			gamma[i] = inv(prd, 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] % mod[i] + 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] % MOD + v[i]) % MOD;
		}
		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[] NTTMODULO = new long[] { 924844033, 962592769, 975175681, 950009857 };
		long[] NTTROOT = new long[] { 5, 7, 17, 7 };

		long[] val;
		long MODULO = -1;
		long root = -1;
		int intLen = 0;

		// 任意剰余で計算する
		public Poly(long MODULO_, long[] vs) {
			val = Arrays.copyOf(vs, vs.length);
			MODULO = MODULO_;
			intLen = val.length;
			for (int i = 0; i < val.length; ++i) {
				val[i] %= MODULO_;
				if (val[i] < 0)
					val[i] += MODULO_;
			}
		}

		public Poly(long MODULO_, long root_, long[] vs) {
			val = Arrays.copyOf(vs, vs.length);
			intLen = val.length;
			MODULO = MODULO_;
			root = root_;
			for (int i = 0; i < val.length; ++i) {
				val[i] %= MODULO_;
				if (val[i] < 0)
					val[i] += MODULO_;
			}
		}

		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;
				if (val[i] < 0)
					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;
				if (val[i] >= MODULO)
					val[i] -= MODULO;
			}
			intLen = 0;
			for (int i = 0; i < val.length; ++i) {
				if (val[i] != 0 && intLen < i + 1)
					intLen = i + 1;
			}
		}

		void mulFFTwithAnyMOD(Poly a) {
			Poly[] ps1 = new Poly[3];
			Poly[] ps2 = new Poly[3];
			int maxLen = 0;
			for (int i = 0; i < ps1.length; ++i) {
				ps1[i] = new Poly(NTTMODULO[i], NTTROOT[i], val);
				ps2[i] = new Poly(NTTMODULO[i], NTTROOT[i], a.val);
				ps1[i].mulFFT(ps2[i]);
				maxLen = Math.max(maxLen, ps1[i].intLen);
			}

			val = new long[maxLen];
			for (int i = 0; i < maxLen; ++i) {
				val[i] = garner(new long[] { ps1[0].val[i], ps1[1].val[i], ps1[2].val[i] }, NTTMODULO, MODULO);
			}
			update();
		}

		void mulNaive(Poly a) {
			if (intLen == 0 || a.intLen == 0) {
				val = new long[] { 0 };
				update();
				return;
			}
			long[] nv = new long[intLen + a.intLen - 1];
			for (int i = 0; i < intLen; ++i) {
				for (int j = 0; j < a.intLen; ++j) {
					nv[i + j] += val[i] % MODULO * a.val[j] % MODULO;
					nv[i + j] %= MODULO;
					if (nv[i + j] < 0)
						nv[i + j] += MODULO;
				}
			}
			val = nv;
			update();
		}

		void mulFFT(Poly a) {
			if (root == -1) {
				mulFFTwithAnyMOD(a);
				return;
			}

			if (a.intLen == 0 || intLen == 0) {
				intLen = 0;
				val = new long[] { 0 };
				return;
			}
			val = mul(val, a.val);
			update();
			return;
		}

		void update() {
			intLen = 0;
			for (int i = 0; i < val.length; ++i) {
				if (val[i] != 0 && intLen < i + 1)
					intLen = i + 1;
			}
		}

		// 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, new long[] { 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, new long[] { 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, new long[] { 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

結果

テストケース

ソースコード