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

提出ソース

結果

問題	No.569 3 x N グリッドのパスの数
ユーザー	37zigen
提出日時	2017-09-09 02:13:19
言語	Java21 (openjdk 21)
結果	AC
実行時間	176 ms / 2,000 ms
コード長	4,896 bytes
コンパイル時間	3,150 ms
コンパイル使用メモリ	88,680 KB
実行使用メモリ	41,876 KB
最終ジャッジ日時	2024-11-07 12:45:00
合計ジャッジ時間	13,419 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	122 ms 40,360 KB
testcase_01	AC	119 ms 40,056 KB
testcase_02	AC	129 ms 41,452 KB
testcase_03	AC	115 ms 40,340 KB
testcase_04	AC	115 ms 40,304 KB
testcase_05	AC	132 ms 41,184 KB
testcase_06	AC	128 ms 41,196 KB
testcase_07	AC	131 ms 41,800 KB
testcase_08	AC	130 ms 41,356 KB
testcase_09	AC	130 ms 41,152 KB
testcase_10	AC	117 ms 40,452 KB
testcase_11	AC	131 ms 41,420 KB
testcase_12	AC	131 ms 41,144 KB
testcase_13	AC	130 ms 41,152 KB
testcase_14	AC	129 ms 41,408 KB
testcase_15	AC	128 ms 41,496 KB
testcase_16	AC	130 ms 41,160 KB
testcase_17	AC	129 ms 41,112 KB
testcase_18	AC	131 ms 41,160 KB
testcase_19	AC	120 ms 40,460 KB
testcase_20	AC	171 ms 41,760 KB
testcase_21	AC	155 ms 41,428 KB
testcase_22	AC	167 ms 41,540 KB
testcase_23	AC	167 ms 41,636 KB
testcase_24	AC	156 ms 41,508 KB
testcase_25	AC	143 ms 41,648 KB
testcase_26	AC	153 ms 41,328 KB
testcase_27	AC	147 ms 41,616 KB
testcase_28	AC	156 ms 41,636 KB
testcase_29	AC	170 ms 41,492 KB
testcase_30	AC	162 ms 41,436 KB
testcase_31	AC	164 ms 41,448 KB
testcase_32	AC	152 ms 41,284 KB
testcase_33	AC	171 ms 41,568 KB
testcase_34	AC	165 ms 41,552 KB
testcase_35	AC	145 ms 41,080 KB
testcase_36	AC	145 ms 41,608 KB
testcase_37	AC	152 ms 41,360 KB
testcase_38	AC	152 ms 41,160 KB
testcase_39	AC	160 ms 41,580 KB
testcase_40	AC	165 ms 41,620 KB
testcase_41	AC	147 ms 41,476 KB
testcase_42	AC	146 ms 41,876 KB
testcase_43	AC	169 ms 41,580 KB
testcase_44	AC	167 ms 41,496 KB
testcase_45	AC	168 ms 41,588 KB
testcase_46	AC	176 ms 41,652 KB
testcase_47	AC	155 ms 41,644 KB
testcase_48	AC	153 ms 41,300 KB
testcase_49	AC	152 ms 41,336 KB
testcase_50	AC	169 ms 41,792 KB
testcase_51	AC	159 ms 41,444 KB
testcase_52	AC	146 ms 41,608 KB
testcase_53	AC	165 ms 41,680 KB
testcase_54	AC	146 ms 41,396 KB
testcase_55	AC	156 ms 41,612 KB
testcase_56	AC	170 ms 41,420 KB
testcase_57	AC	167 ms 41,400 KB
testcase_58	AC	148 ms 41,656 KB
testcase_59	AC	171 ms 41,828 KB

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

ソースコード

raw source code

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 = mul(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[][] ret = new long[a.length][a.length];
		for (int i = 0; i < a.length; ++i) {
			ret[i][i] = 1;
		}
		for (; n > 0; n >>= 1, a = mul(a, a)) {
			if (n % 2 == 1) {
				ret = mul(ret, a);
			}
		}
		return ret;
	}

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

}

yukicoder

結果

テストケース

ソースコード