結果

問題 No.569 3 x N グリッドのパスの数
ユーザー 37zigen37zigen
提出日時 2017-09-12 23:35:47
言語 Java21
(openjdk 21)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 4,789 bytes
コンパイル時間 2,897 ms
コンパイル使用メモリ 88,324 KB
実行使用メモリ 41,812 KB
最終ジャッジ日時 2024-11-07 17:29:04
合計ジャッジ時間 13,862 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 140 ms
41,556 KB
testcase_01 AC 125 ms
40,208 KB
testcase_02 AC 142 ms
41,440 KB
testcase_03 AC 140 ms
41,084 KB
testcase_04 AC 140 ms
41,320 KB
testcase_05 AC 136 ms
41,392 KB
testcase_06 AC 140 ms
41,516 KB
testcase_07 AC 137 ms
41,472 KB
testcase_08 AC 127 ms
40,200 KB
testcase_09 AC 139 ms
41,548 KB
testcase_10 AC 141 ms
41,364 KB
testcase_11 AC 142 ms
41,216 KB
testcase_12 AC 142 ms
41,244 KB
testcase_13 AC 144 ms
41,516 KB
testcase_14 AC 142 ms
41,220 KB
testcase_15 AC 139 ms
41,576 KB
testcase_16 AC 139 ms
41,480 KB
testcase_17 AC 141 ms
41,556 KB
testcase_18 AC 126 ms
40,208 KB
testcase_19 AC 139 ms
41,128 KB
testcase_20 AC 163 ms
41,716 KB
testcase_21 AC 179 ms
41,720 KB
testcase_22 AC 158 ms
41,584 KB
testcase_23 AC 157 ms
41,460 KB
testcase_24 AC 159 ms
41,552 KB
testcase_25 AC 170 ms
41,472 KB
testcase_26 AC 160 ms
41,728 KB
testcase_27 AC 173 ms
41,576 KB
testcase_28 AC 168 ms
41,680 KB
testcase_29 AC 159 ms
41,672 KB
testcase_30 AC 160 ms
41,300 KB
testcase_31 AC 174 ms
41,416 KB
testcase_32 AC 178 ms
41,412 KB
testcase_33 AC 179 ms
41,312 KB
testcase_34 AC 169 ms
41,792 KB
testcase_35 AC 177 ms
41,320 KB
testcase_36 AC 158 ms
41,364 KB
testcase_37 AC 153 ms
41,100 KB
testcase_38 AC 173 ms
41,792 KB
testcase_39 AC 158 ms
41,608 KB
testcase_40 AC 173 ms
41,568 KB
testcase_41 AC 181 ms
41,648 KB
testcase_42 AC 177 ms
41,724 KB
testcase_43 AC 173 ms
41,620 KB
testcase_44 AC 175 ms
41,684 KB
testcase_45 AC 182 ms
41,644 KB
testcase_46 AC 180 ms
41,812 KB
testcase_47 AC 180 ms
41,612 KB
testcase_48 AC 150 ms
41,536 KB
testcase_49 AC 168 ms
41,544 KB
testcase_50 AC 149 ms
41,336 KB
testcase_51 AC 168 ms
41,572 KB
testcase_52 AC 170 ms
41,496 KB
testcase_53 AC 179 ms
41,352 KB
testcase_54 AC 180 ms
41,524 KB
testcase_55 AC 181 ms
41,520 KB
testcase_56 AC 172 ms
41,600 KB
testcase_57 AC 173 ms
41,612 KB
testcase_58 AC 172 ms
41,740 KB
testcase_59 AC 177 ms
41,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
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);
		PrintWriter pw = new PrintWriter(System.out);
		long n = sc.nextLong();
		ArrayList<int[]> list = new ArrayList<>();
		HashMap<List<Integer>, Integer> index = new HashMap<>();
		int idx = 0;
		for (int i = 0; i <= 2; ++i) {
			for (int j = 0; j <= 2; ++j) {
				for (int k = 0; k <= 2; ++k) {
					for (int l = 0; l <= 2; ++l) {
						if (!ok(new int[] { i, j, k, l }))
							continue;
						list.add(new int[] { i, j, k, l });
						index.put(Arrays.asList(i, j, k, l), idx);
						++idx;
					}
				}
			}
		}

		long[][] mat = new long[16][16];
		// mat[x][y]=x->yへの遷移数

		for (int i = 0; i < list.size(); ++i) {
			int[] cur = list.get(i);
			ArrayDeque<int[]> pend = new ArrayDeque<>();
			ArrayDeque<int[]> pend2 = new ArrayDeque<>();
			pend.add(cur);
			pend2.add(cur);
			mat[index.get(toList(cur))][index.get(toList(cur))]++;

			while (!pend.isEmpty()) {
				int[] p = pend.pollFirst();
				int src = -1;
				for (int j = 0; j < 4; ++j)
					if (p[j] == 1)
						src = j;

				// 1を移動
				for (int d = -1; d <= 1; d += 2) {
					int nsrc = src + d;
					if (!(0 <= nsrc && nsrc <= 3) || p[nsrc] == -1)
						continue;
					int[] dst = Arrays.copyOf(p, p.length);
					dst[nsrc] = 1;
					dst[src] = -1;
					for (int j = 0; j < 4; ++j) {
						if (dst[j] == 2 && p[nsrc] == 2) {
							dst[j] = 1;
							dst[nsrc] = -1;
						}
					}
					if (!ok(dst)) {
						throw new AssertionError();
					}
					pend.add(dst);
					pend2.add(dst);
					dst = regulate(dst);
					mat[index.get(toList(dst))][index.get(toList(cur))]++;
				}

				// 2を伸ばす
				while (!pend2.isEmpty()) {
					int[] p2 = pend2.poll();
					for (int j = 0; j < 4; ++j) {
						if (p2[j] != 2)
							continue;
						for (int d = -1; d <= 1; d += 2) {
							int nj = j + d;
							if (!(0 <= nj && nj < 4) || p2[nj] != 0) {
								continue;
							}
							int[] dst = Arrays.copyOf(p2, p2.length);
							dst[j] = -1;
							dst[nj] = 2;
							if (!ok(dst)) {
								throw new AssertionError();
							}
							pend2.add(dst);
							dst = regulate(dst);
							mat[index.get(toList(dst))][index.get(toList(cur))]++;
						}

					}
				}

				// 2を生成
				for (int j = 0; j < 4; ++j) {
					loop: for (int k = j + 1; k < 4; ++k) {
						for (int l = j; l <= k; ++l) {
							if (p[l] != 0)
								continue loop;
						}
						int[] dst = Arrays.copyOf(p, p.length);
						for (int l = j; l <= k; ++l) {
							dst[l] = -1;
						}
						dst[j] = 2;
						dst[k] = 2;
						if (!ok(dst)) {
							throw new AssertionError();
						}
						dst = regulate(dst);
						mat[index.get(toList(dst))][index.get(toList(cur))]++;
					}
				}
			}
		}

		long[][] v = new long[16][1];
		int curIdx = index.get(Arrays.asList(1, 0, 0, 0));
		int lastIdx = index.get(Arrays.asList(0, 0, 0, 1));
		v[curIdx][0]++;
		v = pow(mat, n + 1, v);
		System.out.println(v[lastIdx][0]);

	}

	boolean ok(int[] arr) {

		int c2 = count(2, 0, 3, arr);
		if (!(c2 == 0 || c2 == 2))
			return false;

		int c1 = count(1, 0, 3, arr);
		if (c1 != 1)
			return false;

		for (int i = 0; i < 4; ++i) {
			for (int j = i + 1; j < 4; ++j) {
				if (arr[i] != 2 || arr[j] != 2)
					continue;
				for (int k = i + 1; k < j; ++k) {
					if (arr[k] == 1)
						return false;
				}
			}
		}
		return true;
	}

	int count(int val, int s, int t, int[] arr) {
		int ret = 0;
		for (int i = s; i <= t; ++i) {
			if (arr[i] == val)
				++ret;
		}
		return ret;
	}

	long[][] mul(long[][] a, long[][] b) {
		long[][] ret = new long[a.length][b[0].length];
		for (int i = 0; i < a.length; ++i) {
			for (int j = 0; j < b[i].length; ++j) {
				for (int k = 0; k < a[0].length; ++k) {
					ret[i][j] += a[i][k] * b[k][j] % MODULO;
					ret[i][j] %= MODULO;
				}
			}
		}
		return ret;
	}

	long[][] pow(long[][] a, long n, long[][] v) {
		for (; n > 0; n >>= 1, a = mul(a, a)) {
			if (n % 2 == 1) {
				v = mul(a, v);
			}
		}
		return v;
	}

	ArrayList<Integer> toList(int[] arr) {
		ArrayList<Integer> ret = new ArrayList<>();
		for (int i = 0; i < arr.length; ++i) {
			ret.add(arr[i]);
		}
		return ret;
	}

	int[] regulate(int[] arr) {
		int[] ret = Arrays.copyOf(arr, arr.length);
		for (int i = 0; i < arr.length; ++i) {
			if (ret[i] == -1)
				ret[i] = 0;
		}
		return ret;
	}

	final long MODULO = 1_000_000_000 + 7;

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

}
0