結果
問題 | No.621 3 x N グリッド上のドミノの置き方の数 |
ユーザー | maspy |
提出日時 | 2020-04-08 14:25:16 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,336 ms / 3,000 ms |
コード長 | 1,893 bytes |
コンパイル時間 | 95 ms |
コンパイル使用メモリ | 11,240 KB |
実行使用メモリ | 31,460 KB |
最終ジャッジ日時 | 2023-09-25 15:02:37 |
合計ジャッジ時間 | 60,748 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 191 ms
30,912 KB |
testcase_01 | AC | 230 ms
31,188 KB |
testcase_02 | AC | 179 ms
29,840 KB |
testcase_03 | AC | 190 ms
30,904 KB |
testcase_04 | AC | 202 ms
31,104 KB |
testcase_05 | AC | 202 ms
31,324 KB |
testcase_06 | AC | 212 ms
31,352 KB |
testcase_07 | AC | 211 ms
31,188 KB |
testcase_08 | AC | 221 ms
31,248 KB |
testcase_09 | AC | 212 ms
31,344 KB |
testcase_10 | AC | 221 ms
31,180 KB |
testcase_11 | AC | 220 ms
31,160 KB |
testcase_12 | AC | 271 ms
31,232 KB |
testcase_13 | AC | 293 ms
31,116 KB |
testcase_14 | AC | 362 ms
31,172 KB |
testcase_15 | AC | 431 ms
31,244 KB |
testcase_16 | AC | 471 ms
31,116 KB |
testcase_17 | AC | 481 ms
31,336 KB |
testcase_18 | AC | 579 ms
31,352 KB |
testcase_19 | AC | 590 ms
31,328 KB |
testcase_20 | AC | 647 ms
31,252 KB |
testcase_21 | AC | 669 ms
31,056 KB |
testcase_22 | AC | 757 ms
31,372 KB |
testcase_23 | AC | 774 ms
31,208 KB |
testcase_24 | AC | 826 ms
31,184 KB |
testcase_25 | AC | 933 ms
31,388 KB |
testcase_26 | AC | 913 ms
31,176 KB |
testcase_27 | AC | 1,022 ms
31,324 KB |
testcase_28 | AC | 1,024 ms
31,388 KB |
testcase_29 | AC | 1,092 ms
31,064 KB |
testcase_30 | AC | 1,041 ms
31,408 KB |
testcase_31 | AC | 1,015 ms
31,332 KB |
testcase_32 | AC | 965 ms
31,360 KB |
testcase_33 | AC | 1,083 ms
31,288 KB |
testcase_34 | AC | 1,041 ms
31,144 KB |
testcase_35 | AC | 1,000 ms
31,344 KB |
testcase_36 | AC | 1,038 ms
31,196 KB |
testcase_37 | AC | 1,116 ms
31,068 KB |
testcase_38 | AC | 1,133 ms
31,176 KB |
testcase_39 | AC | 1,146 ms
31,380 KB |
testcase_40 | AC | 1,147 ms
31,332 KB |
testcase_41 | AC | 1,155 ms
31,308 KB |
testcase_42 | AC | 1,128 ms
31,276 KB |
testcase_43 | AC | 1,131 ms
31,460 KB |
testcase_44 | AC | 1,138 ms
31,204 KB |
testcase_45 | AC | 1,142 ms
31,332 KB |
testcase_46 | AC | 1,131 ms
31,188 KB |
testcase_47 | AC | 1,146 ms
31,184 KB |
testcase_48 | AC | 1,141 ms
31,180 KB |
testcase_49 | AC | 1,155 ms
31,112 KB |
testcase_50 | AC | 1,131 ms
31,364 KB |
testcase_51 | AC | 1,148 ms
31,404 KB |
testcase_52 | AC | 1,144 ms
31,340 KB |
testcase_53 | AC | 1,153 ms
31,188 KB |
testcase_54 | AC | 1,143 ms
31,168 KB |
testcase_55 | AC | 1,155 ms
31,172 KB |
testcase_56 | AC | 1,153 ms
31,360 KB |
testcase_57 | AC | 1,161 ms
31,180 KB |
testcase_58 | AC | 997 ms
31,312 KB |
testcase_59 | AC | 1,311 ms
31,336 KB |
testcase_60 | AC | 1,320 ms
31,332 KB |
testcase_61 | AC | 1,319 ms
31,164 KB |
testcase_62 | AC | 1,336 ms
31,168 KB |
testcase_63 | AC | 767 ms
31,320 KB |
testcase_64 | AC | 777 ms
31,348 KB |
testcase_65 | AC | 773 ms
31,332 KB |
testcase_66 | AC | 788 ms
31,144 KB |
testcase_67 | AC | 775 ms
31,364 KB |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import itertools import numpy as np MOD = 10 ** 9 + 7 # 0: empty, 1~: RULD def cnt_mat(i, j): x1, y1, z1 = i % 5, (i // 5) % 5, i // 25 x2, y2, z2 = j % 5, (j // 5) % 5, j // 25 # 2つ連続の空マスは許容しない if any(s == t == 0 for s, t in ((x1, x2), (y1, y2), (z1, z2), (x1, y1), (y1, z1), (x2, y2), (y2, z2))): return 0 # 貼り合わせ右 if any(s == 1 and t != 3 for s, t in ((x1, x2), (y1, y2), (z1, z2))): return 0 # 貼り合わせ左 if any(s == 3 and t != 1 for s, t in ((x2, x1), (y2, y1), (z2, z1))): return 0 # 貼り合わせ下 if any(s == 4 and t != 2 for s, t in ((x1, y1), (y1, z1), (x2, y2), (y2, z2))): return 0 # 貼り合わせ上 if any(s != 4 and t == 2 for s, t in ((x1, y1), (y1, z1), (x2, y2), (y2, z2))): return 0 # はみ出し if x1 == 2 or x2 == 2 or z1 == 4 or z2 == 4: return 0 return 1 mat = np.zeros((125, 125), np.int64) for i, j in itertools.product(range(125), repeat=2): mat[i, j] = cnt_mat(i, j) def mat_mul(A, B): mask = (1 << 15) - 1 A1 = A >> 15 A2 = A & mask B1 = B >> 15 B2 = B & mask X = np.dot(A1, B1) % MOD Y = np.dot(A2, B2) % MOD Z = (np.dot(A1 + A2, B1 + B2) - X - Y) % MOD W = (np.dot(A1, B2) + np.dot(A2, B1)) % MOD return ((X << 30) + (Z << 15) + Y) % MOD def power(A, n): if n == 1: return A B = power(A, n // 2) B = mat_mul(B, B) return mat_mul(A, B) if n & 1 else B N = int(read()) init = 93 A = power(mat, N)[init, :] answer = 0 for i in range(125): x, y, z = i % 5, (i // 5) % 5, i // 25 if x != 1 and y != 1 and z != 1 and A[i] != 0: answer += A[i] answer %= MOD print(answer)