結果

問題 No.569 3 x N グリッドのパスの数
ユーザー 37zigen37zigen
提出日時 2017-09-12 23:34:05
言語 Java21
(openjdk 21)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 5,049 bytes
コンパイル時間 2,225 ms
コンパイル使用メモリ 82,624 KB
実行使用メモリ 41,848 KB
最終ジャッジ日時 2024-04-25 07:12:40
合計ジャッジ時間 11,609 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 113 ms
41,492 KB
testcase_01 AC 114 ms
41,384 KB
testcase_02 AC 110 ms
40,272 KB
testcase_03 AC 112 ms
41,280 KB
testcase_04 AC 108 ms
40,380 KB
testcase_05 AC 112 ms
40,208 KB
testcase_06 AC 116 ms
41,248 KB
testcase_07 AC 112 ms
41,224 KB
testcase_08 AC 107 ms
40,432 KB
testcase_09 AC 115 ms
41,256 KB
testcase_10 AC 115 ms
41,600 KB
testcase_11 AC 110 ms
40,848 KB
testcase_12 AC 106 ms
40,408 KB
testcase_13 AC 109 ms
39,964 KB
testcase_14 AC 112 ms
41,444 KB
testcase_15 AC 98 ms
40,060 KB
testcase_16 AC 113 ms
41,348 KB
testcase_17 AC 116 ms
41,300 KB
testcase_18 AC 120 ms
40,460 KB
testcase_19 AC 116 ms
39,948 KB
testcase_20 AC 133 ms
41,532 KB
testcase_21 AC 140 ms
41,436 KB
testcase_22 AC 132 ms
41,220 KB
testcase_23 AC 131 ms
41,444 KB
testcase_24 AC 130 ms
41,496 KB
testcase_25 AC 138 ms
41,316 KB
testcase_26 AC 131 ms
41,464 KB
testcase_27 AC 149 ms
41,288 KB
testcase_28 AC 147 ms
41,344 KB
testcase_29 AC 135 ms
41,840 KB
testcase_30 AC 132 ms
41,516 KB
testcase_31 AC 141 ms
41,364 KB
testcase_32 AC 137 ms
41,428 KB
testcase_33 AC 136 ms
41,192 KB
testcase_34 AC 131 ms
41,632 KB
testcase_35 AC 132 ms
41,228 KB
testcase_36 AC 132 ms
41,760 KB
testcase_37 AC 132 ms
41,556 KB
testcase_38 AC 131 ms
41,464 KB
testcase_39 AC 142 ms
41,720 KB
testcase_40 AC 152 ms
41,772 KB
testcase_41 AC 150 ms
41,508 KB
testcase_42 AC 152 ms
41,460 KB
testcase_43 AC 152 ms
41,624 KB
testcase_44 AC 153 ms
41,484 KB
testcase_45 AC 152 ms
41,592 KB
testcase_46 AC 157 ms
41,848 KB
testcase_47 AC 156 ms
41,512 KB
testcase_48 AC 130 ms
41,328 KB
testcase_49 AC 139 ms
41,492 KB
testcase_50 AC 153 ms
41,580 KB
testcase_51 AC 158 ms
41,704 KB
testcase_52 AC 154 ms
41,632 KB
testcase_53 AC 150 ms
41,548 KB
testcase_54 AC 147 ms
41,384 KB
testcase_55 AC 131 ms
41,712 KB
testcase_56 AC 157 ms
41,464 KB
testcase_57 AC 153 ms
41,476 KB
testcase_58 AC 137 ms
41,420 KB
testcase_59 AC 161 ms
41,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Scanner;

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