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

提出ソース

結果

問題	No.569 3 x N グリッドのパスの数
ユーザー	37zigen
提出日時	2017-09-12 23:34:05
言語	Java21 (openjdk 21)
結果	AC
実行時間	182 ms / 2,000 ms
コード長	5,049 bytes
コンパイル時間	3,081 ms
コンパイル使用メモリ	89,248 KB
実行使用メモリ	41,796 KB
最終ジャッジ日時	2024-11-07 17:28:16
合計ジャッジ時間	14,135 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	138 ms 41,444 KB
testcase_01	AC	124 ms 40,184 KB
testcase_02	AC	123 ms 40,304 KB
testcase_03	AC	137 ms 41,424 KB
testcase_04	AC	121 ms 40,072 KB
testcase_05	AC	124 ms 40,136 KB
testcase_06	AC	142 ms 41,696 KB
testcase_07	AC	138 ms 41,472 KB
testcase_08	AC	137 ms 41,216 KB
testcase_09	AC	139 ms 41,304 KB
testcase_10	AC	123 ms 40,404 KB
testcase_11	AC	141 ms 41,324 KB
testcase_12	AC	138 ms 41,080 KB
testcase_13	AC	140 ms 41,348 KB
testcase_14	AC	141 ms 41,292 KB
testcase_15	AC	138 ms 41,280 KB
testcase_16	AC	124 ms 40,084 KB
testcase_17	AC	138 ms 41,372 KB
testcase_18	AC	126 ms 40,432 KB
testcase_19	AC	139 ms 41,272 KB
testcase_20	AC	156 ms 41,456 KB
testcase_21	AC	172 ms 41,364 KB
testcase_22	AC	157 ms 41,772 KB
testcase_23	AC	159 ms 41,644 KB
testcase_24	AC	174 ms 41,288 KB
testcase_25	AC	160 ms 41,260 KB
testcase_26	AC	159 ms 41,580 KB
testcase_27	AC	162 ms 41,396 KB
testcase_28	AC	157 ms 41,464 KB
testcase_29	AC	151 ms 41,016 KB
testcase_30	AC	162 ms 41,628 KB
testcase_31	AC	151 ms 41,228 KB
testcase_32	AC	172 ms 41,492 KB
testcase_33	AC	156 ms 41,216 KB
testcase_34	AC	170 ms 41,516 KB
testcase_35	AC	159 ms 41,440 KB
testcase_36	AC	160 ms 41,532 KB
testcase_37	AC	160 ms 41,732 KB
testcase_38	AC	159 ms 41,484 KB
testcase_39	AC	155 ms 41,420 KB
testcase_40	AC	174 ms 41,508 KB
testcase_41	AC	177 ms 41,604 KB
testcase_42	AC	180 ms 41,564 KB
testcase_43	AC	178 ms 41,580 KB
testcase_44	AC	182 ms 41,744 KB
testcase_45	AC	182 ms 41,196 KB
testcase_46	AC	180 ms 41,352 KB
testcase_47	AC	180 ms 41,388 KB
testcase_48	AC	179 ms 41,492 KB
testcase_49	AC	173 ms 41,588 KB
testcase_50	AC	157 ms 41,472 KB
testcase_51	AC	181 ms 41,228 KB
testcase_52	AC	179 ms 41,328 KB
testcase_53	AC	179 ms 41,336 KB
testcase_54	AC	177 ms 41,452 KB
testcase_55	AC	181 ms 41,796 KB
testcase_56	AC	179 ms 41,692 KB
testcase_57	AC	182 ms 41,328 KB
testcase_58	AC	153 ms 41,300 KB
testcase_59	AC	181 ms 41,252 KB

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

ソースコード

raw source code

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

}

yukicoder

結果

テストケース

ソースコード