結果

問題 No.569 3 x N グリッドのパスの数
コンテスト
ユーザー 37zigen
提出日時 2017-09-14 01:22:08
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 7,571 bytes
コンパイル時間 2,723 ms
コンパイル使用メモリ 80,248 KB
実行使用メモリ 47,516 KB
最終ジャッジ日時 2024-11-07 21:07:35
合計ジャッジ時間 19,043 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

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);
		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[] NTTMODULO = new long[] { 1012924417L, 1004535809L, 975175681L };
	long[] NTTROOT = new long[] { 5, 3, 17 };

	long nthMod(long[] coe, long[] init, long n, long MODULO) {
		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], 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);
			}
			for (int j = 0; j < ret.intLen; ++j) {
				ans[i] += ret.val[j] * (init[j] % NTTMODULO[i]) % NTTMODULO[i];
				if (ans[i] >= NTTMODULO[i])
					ans[i] -= NTTMODULO[i];
			}
		}
		return garner(ans, NTTMODULO, MODULO);
	}

	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] + 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]) % 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[] 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;
				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 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));
	}

}
0