結果

問題 No.621 3 x N グリッド上のドミノの置き方の数
コンテスト
ユーザー しらっ亭
提出日時 2017-12-01 19:26:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 100 ms / 3,000 ms
コード長 2,411 bytes
コンパイル時間 1,940 ms
コンパイル使用メモリ 168,356 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 22:45:04
合計ジャッジ時間 7,446 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 66
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=int(a);i<int(b);++i)

const int mod = 1e9 + 7;

using Mat = array<array<int64_t, 64>, 64>;

Mat matMul(const Mat &l, const Mat &r) {
	Mat ret {};
	for (int i = 0; i < 64; i++) {
		for (int k = 0; k < 64; k++) {
			for (int j = 0; j < 64; j++) {
				(ret[i][j] += (l[i][k] * r[k][j]) % mod + mod) %= mod;
			}
		}
	}
	return ret;
}

Mat matPow(Mat A, int64_t m) {
	Mat B {};
	rep(i, 0, 64) B[i][i] = 1;
	while (m > 0) {
		if (m & 1) B = matMul(B, A);
		A = matMul(A, A);
		m >>= 1;
	}
	return B;
}

int main() {
	int64_t n;
	cin >> n;

	Mat mat {};

	int b3 = 1 << 3;

	rep(i, 0, b3) {
		bool i0 = (i & 1) != 0;
		bool i1 = (i & 2) != 0;
		bool i2 = (i & 4) != 0;
		rep(j, 0, b3) {
			bool j0 = (j & 1) != 0;
			bool j1 = (j & 2) != 0;
			bool j2 = (j & 4) != 0;

			int from = (j << 3) | i;

			rep(p0, 0, 2) {
				if (i0 && p0) continue;
				if (!j0 && !p0) continue;
				rep(p1, 0, 2) {
					if (i1 && p1) continue;
					if (!j1 && !p1) continue;
					rep(p2, 0, 2) {
						if (i2 && p2) continue;
						if (!j2 && !p2) continue;

						if ((i0 | p0) == 0 && (i1 | p1) == 0) continue;
						if ((i2 | p2) == 0 && (i1 | p1) == 0) continue;

						int y = (p2 << 2) + (p1 << 1) + p0;
						int x = y | i;
						int to = (x << 3) | y;
						mat[from][to]++;
					}
				}
			}

			if (!i0 && !i1) {
				if (i2) {
					int x = 3 + (1 << 2);
					int y = 0 + (0 << 2);
					int to = (x << 3) | y;
					mat[from][to]++;
				}
				else if (j2) {
					rep(p2, 0, 2) {
						int x = 3 + (p2 << 2);
						int y = 0 + (p2 << 2);
						int to = (x << 3) | y;
						mat[from][to]++;
					}
				}
				else {
					int x = 3 + (1 << 2);
					int y = 0 + (1 << 2);
					int to = (x << 3) | y;
					mat[from][to]++;
				}
			}

			if (!i1 && !i2) {
				if (i0) {
					int x = 6 + (1 << 0);
					int y = 0 + (0 << 0);
					int to = (x << 3) | y;
					mat[from][to]++;
				}
				else if (j0) {
					rep(p2, 0, 2) {
						int x = 6 + (p2 << 0);
						int y = 0 + (p2 << 0);
						int to = (x << 3) | y;
						mat[from][to]++;
					}
				}
				else {
					int x = 6 + (1 << 0);
					int y = 0 + (1 << 0);
					int to = (x << 3) | y;
					mat[from][to]++;
				}
			}
		}
	}

	mat = matPow(mat, n);

	int64_t ans = 0;
	rep(j, 2, b3) {
		if (j == 4) continue;
		int from = j << 3;
		(ans += mat[0b111000][from]) %= mod;
	}

	cout << ans << endl;
	return 0;
}
0