結果

問題 No.569 3 x N グリッドのパスの数
ユーザー 37zigen37zigen
提出日時 2017-09-14 04:29:11
言語 Java21
(openjdk 21)
結果
AC  
実行時間 455 ms / 2,000 ms
コード長 9,045 bytes
コンパイル時間 3,882 ms
コンパイル使用メモリ 87,832 KB
実行使用メモリ 48,964 KB
最終ジャッジ日時 2024-11-07 21:11:04
合計ジャッジ時間 22,344 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 135 ms
41,420 KB
testcase_01 AC 133 ms
41,212 KB
testcase_02 AC 133 ms
41,224 KB
testcase_03 AC 127 ms
41,152 KB
testcase_04 AC 130 ms
41,320 KB
testcase_05 AC 130 ms
41,216 KB
testcase_06 AC 124 ms
40,228 KB
testcase_07 AC 135 ms
41,500 KB
testcase_08 AC 134 ms
41,060 KB
testcase_09 AC 135 ms
41,508 KB
testcase_10 AC 136 ms
41,208 KB
testcase_11 AC 135 ms
41,204 KB
testcase_12 AC 138 ms
41,544 KB
testcase_13 AC 140 ms
41,356 KB
testcase_14 AC 129 ms
40,128 KB
testcase_15 AC 130 ms
40,240 KB
testcase_16 AC 139 ms
41,468 KB
testcase_17 AC 132 ms
41,092 KB
testcase_18 AC 145 ms
41,644 KB
testcase_19 AC 148 ms
41,488 KB
testcase_20 AC 288 ms
45,164 KB
testcase_21 AC 290 ms
45,192 KB
testcase_22 AC 289 ms
45,036 KB
testcase_23 AC 283 ms
45,432 KB
testcase_24 AC 282 ms
45,356 KB
testcase_25 AC 284 ms
45,016 KB
testcase_26 AC 280 ms
46,812 KB
testcase_27 AC 283 ms
45,008 KB
testcase_28 AC 283 ms
45,388 KB
testcase_29 AC 273 ms
45,044 KB
testcase_30 AC 288 ms
45,380 KB
testcase_31 AC 286 ms
45,188 KB
testcase_32 AC 297 ms
45,320 KB
testcase_33 AC 293 ms
45,312 KB
testcase_34 AC 292 ms
45,252 KB
testcase_35 AC 286 ms
44,988 KB
testcase_36 AC 279 ms
46,344 KB
testcase_37 AC 288 ms
45,136 KB
testcase_38 AC 293 ms
45,084 KB
testcase_39 AC 297 ms
46,904 KB
testcase_40 AC 396 ms
47,484 KB
testcase_41 AC 439 ms
48,092 KB
testcase_42 AC 451 ms
48,964 KB
testcase_43 AC 448 ms
47,888 KB
testcase_44 AC 449 ms
47,716 KB
testcase_45 AC 441 ms
47,836 KB
testcase_46 AC 440 ms
47,700 KB
testcase_47 AC 439 ms
47,992 KB
testcase_48 AC 435 ms
48,920 KB
testcase_49 AC 430 ms
48,700 KB
testcase_50 AC 438 ms
47,824 KB
testcase_51 AC 427 ms
48,228 KB
testcase_52 AC 433 ms
47,756 KB
testcase_53 AC 455 ms
48,268 KB
testcase_54 AC 432 ms
48,940 KB
testcase_55 AC 438 ms
47,852 KB
testcase_56 AC 435 ms
47,900 KB
testcase_57 AC 431 ms
47,904 KB
testcase_58 AC 436 ms
48,352 KB
testcase_59 AC 425 ms
47,788 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

}
0