結果
問題 | No.621 3 x N グリッド上のドミノの置き方の数 |
ユーザー | しらっ亭 |
提出日時 | 2017-12-08 02:53:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 170 ms / 3,000 ms |
コード長 | 2,142 bytes |
コンパイル時間 | 367 ms |
コンパイル使用メモリ | 82,604 KB |
実行使用メモリ | 76,480 KB |
最終ジャッジ日時 | 2024-05-06 19:50:29 |
合計ジャッジ時間 | 9,903 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
61,932 KB |
testcase_01 | AC | 52 ms
65,380 KB |
testcase_02 | AC | 43 ms
61,768 KB |
testcase_03 | AC | 44 ms
62,340 KB |
testcase_04 | AC | 47 ms
62,580 KB |
testcase_05 | AC | 46 ms
62,324 KB |
testcase_06 | AC | 52 ms
63,580 KB |
testcase_07 | AC | 47 ms
63,716 KB |
testcase_08 | AC | 48 ms
64,692 KB |
testcase_09 | AC | 48 ms
62,896 KB |
testcase_10 | AC | 49 ms
64,288 KB |
testcase_11 | AC | 49 ms
62,888 KB |
testcase_12 | AC | 54 ms
66,264 KB |
testcase_13 | AC | 55 ms
67,848 KB |
testcase_14 | AC | 66 ms
73,040 KB |
testcase_15 | AC | 84 ms
76,076 KB |
testcase_16 | AC | 87 ms
75,756 KB |
testcase_17 | AC | 88 ms
75,828 KB |
testcase_18 | AC | 97 ms
76,052 KB |
testcase_19 | AC | 97 ms
76,100 KB |
testcase_20 | AC | 102 ms
75,816 KB |
testcase_21 | AC | 104 ms
75,884 KB |
testcase_22 | AC | 113 ms
75,836 KB |
testcase_23 | AC | 114 ms
75,948 KB |
testcase_24 | AC | 120 ms
76,036 KB |
testcase_25 | AC | 133 ms
75,976 KB |
testcase_26 | AC | 130 ms
75,844 KB |
testcase_27 | AC | 139 ms
76,132 KB |
testcase_28 | AC | 137 ms
75,940 KB |
testcase_29 | AC | 146 ms
75,864 KB |
testcase_30 | AC | 141 ms
76,008 KB |
testcase_31 | AC | 136 ms
76,124 KB |
testcase_32 | AC | 134 ms
76,176 KB |
testcase_33 | AC | 143 ms
76,072 KB |
testcase_34 | AC | 138 ms
76,092 KB |
testcase_35 | AC | 135 ms
75,820 KB |
testcase_36 | AC | 139 ms
75,836 KB |
testcase_37 | AC | 145 ms
75,956 KB |
testcase_38 | AC | 149 ms
76,480 KB |
testcase_39 | AC | 148 ms
76,172 KB |
testcase_40 | AC | 152 ms
76,276 KB |
testcase_41 | AC | 150 ms
75,816 KB |
testcase_42 | AC | 151 ms
76,032 KB |
testcase_43 | AC | 146 ms
76,144 KB |
testcase_44 | AC | 149 ms
75,908 KB |
testcase_45 | AC | 160 ms
75,924 KB |
testcase_46 | AC | 151 ms
75,980 KB |
testcase_47 | AC | 154 ms
75,932 KB |
testcase_48 | AC | 147 ms
75,816 KB |
testcase_49 | AC | 147 ms
75,832 KB |
testcase_50 | AC | 147 ms
75,940 KB |
testcase_51 | AC | 150 ms
76,012 KB |
testcase_52 | AC | 151 ms
76,204 KB |
testcase_53 | AC | 151 ms
75,984 KB |
testcase_54 | AC | 149 ms
76,020 KB |
testcase_55 | AC | 151 ms
76,052 KB |
testcase_56 | AC | 151 ms
76,024 KB |
testcase_57 | AC | 152 ms
76,176 KB |
testcase_58 | AC | 134 ms
75,732 KB |
testcase_59 | AC | 163 ms
76,424 KB |
testcase_60 | AC | 163 ms
76,076 KB |
testcase_61 | AC | 162 ms
75,800 KB |
testcase_62 | AC | 170 ms
76,268 KB |
testcase_63 | AC | 113 ms
75,772 KB |
testcase_64 | AC | 114 ms
75,956 KB |
testcase_65 | AC | 112 ms
75,960 KB |
testcase_66 | AC | 113 ms
75,932 KB |
testcase_67 | AC | 111 ms
76,288 KB |
ソースコード
mod = 10 ** 9 + 7 range64 = range(64) def mat_mul(l, r): ret = [[0] * 64 for _ in range64] for i in range64: reti = ret[i] li = l[i] for k in range64: lik = li[k] rk = r[k] for j in range64: reti[j] += lik * rk[j] for j in range64: if reti[j] > mod: reti[j] %= mod return ret def mat_pow(A, m): B = [[0] * 64 for _ in range64] for i in range64: B[i][i] = 1 while m: if m & 1: B = mat_mul(B, A) A = mat_mul(A, A) m >>= 1 return B def solve(n): mat = [[0] * 64 for _ in range64] b3 = 8 for i in range(b3): i0 = (i & 1) != 0 i1 = (i & 2) != 0 i2 = (i & 4) != 0 for j in range(b3): j0 = (j & 1) != 0 j1 = (j & 2) != 0 j2 = (j & 4) != 0 fr = (j << 3) | i for p0 in range(2): if i0 and p0: continue if not j0 and not p0: continue for p1 in range(2): if i1 and p1: continue if not j1 and not p1: continue for p2 in range(2): if i2 and p2: continue if not j2 and not p2: continue if (i0 | p0) == 0 and (i1 | p1) == 0: continue if (i2 | p2) == 0 and (i1 | p1) == 0: continue y = (p2 << 2) + (p1 << 1) + p0 x = y | i to = (x << 3) | y mat[fr][to] += 1 if not i0 and not i1: if i2: x = 3 + (1 << 2) y = 0 + (0 << 2) to = (x << 3) | y mat[fr][to] += 1 elif j2: for p2 in range(2): x = 3 + (p2 << 2) y = 0 + (p2 << 2) to = (x << 3) | y mat[fr][to] += 1 else: x = 3 + (1 << 2) y = 0 + (1 << 2) to = (x << 3) | y mat[fr][to] += 1 if not i1 and not i2: if i0: x = 6 + (1 << 0) y = 0 + (0 << 0) to = (x << 3) | y mat[fr][to] += 1 elif j0: for p2 in range(2): x = 6 + (p2 << 0) y = 0 + (p2 << 0) to = (x << 3) | y mat[fr][to] += 1 else: x = 6 + (1 << 0) y = 0 + (1 << 0) to = (x << 3) | y mat[fr][to] += 1 mat = mat_pow(mat, n) ans = 0 for j in range(2, b3): if j == 4: continue fr = j << 3 ans += mat[0b111000][fr] return ans % mod print(solve(int(input())))