#219763 (C++14) No.621 3 x N グリッド上のドミノの置き方の数

提出ソース

結果

問題	No.621 3 x N グリッド上のドミノの置き方の数
ユーザー	しらっ亭
提出日時	2017-12-01 19:26:54
言語	C++14 (gcc 12.3.0 + boost 1.83.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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 5,248 KB
testcase_01	AC	7 ms 5,248 KB
testcase_02	AC	4 ms 5,248 KB
testcase_03	AC	4 ms 5,248 KB
testcase_04	AC	5 ms 5,248 KB
testcase_05	AC	5 ms 5,248 KB
testcase_06	AC	6 ms 5,248 KB
testcase_07	AC	6 ms 5,248 KB
testcase_08	AC	7 ms 5,248 KB
testcase_09	AC	6 ms 5,248 KB
testcase_10	AC	7 ms 5,248 KB
testcase_11	AC	7 ms 5,248 KB
testcase_12	AC	11 ms 5,248 KB
testcase_13	AC	13 ms 5,248 KB
testcase_14	AC	19 ms 5,248 KB
testcase_15	AC	24 ms 5,248 KB
testcase_16	AC	28 ms 5,248 KB
testcase_17	AC	29 ms 5,248 KB
testcase_18	AC	36 ms 5,248 KB
testcase_19	AC	38 ms 5,248 KB
testcase_20	AC	43 ms 5,248 KB
testcase_21	AC	44 ms 5,248 KB
testcase_22	AC	52 ms 5,248 KB
testcase_23	AC	53 ms 5,248 KB
testcase_24	AC	57 ms 5,248 KB
testcase_25	AC	66 ms 5,248 KB
testcase_26	AC	65 ms 5,248 KB
testcase_27	AC	74 ms 5,248 KB
testcase_28	AC	74 ms 5,248 KB
testcase_29	AC	80 ms 5,248 KB
testcase_30	AC	76 ms 5,248 KB
testcase_31	AC	73 ms 5,248 KB
testcase_32	AC	69 ms 5,248 KB
testcase_33	AC	78 ms 5,248 KB
testcase_34	AC	75 ms 5,248 KB
testcase_35	AC	71 ms 5,248 KB
testcase_36	AC	72 ms 5,248 KB
testcase_37	AC	80 ms 5,248 KB
testcase_38	AC	83 ms 5,248 KB
testcase_39	AC	84 ms 5,248 KB
testcase_40	AC	84 ms 5,248 KB
testcase_41	AC	84 ms 5,248 KB
testcase_42	AC	82 ms 5,248 KB
testcase_43	AC	83 ms 5,248 KB
testcase_44	AC	83 ms 5,248 KB
testcase_45	AC	84 ms 5,248 KB
testcase_46	AC	82 ms 5,248 KB
testcase_47	AC	84 ms 5,248 KB
testcase_48	AC	83 ms 5,248 KB
testcase_49	AC	85 ms 5,248 KB
testcase_50	AC	83 ms 5,248 KB
testcase_51	AC	84 ms 5,248 KB
testcase_52	AC	84 ms 5,248 KB
testcase_53	AC	85 ms 5,248 KB
testcase_54	AC	83 ms 5,248 KB
testcase_55	AC	85 ms 5,248 KB
testcase_56	AC	84 ms 5,248 KB
testcase_57	AC	85 ms 5,248 KB
testcase_58	AC	71 ms 5,248 KB
testcase_59	AC	98 ms 5,248 KB
testcase_60	AC	98 ms 5,248 KB
testcase_61	AC	98 ms 5,248 KB
testcase_62	AC	100 ms 5,248 KB
testcase_63	AC	53 ms 5,248 KB
testcase_64	AC	53 ms 5,248 KB
testcase_65	AC	53 ms 5,248 KB
testcase_66	AC	54 ms 5,248 KB
testcase_67	AC	53 ms 5,248 KB

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

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード