結果

問題 No.569 3 x N グリッドのパスの数
コンテスト
ユーザー 37zigen
提出日時 2017-09-09 02:13:19
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

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

}
0