結果
問題 | No.579 3 x N グリッド上のサイクルのサイズ(hard) |
ユーザー | maspy |
提出日時 | 2020-05-06 18:23:41 |
言語 | Python3 (3.11.6 + numpy 1.26.0 + scipy 1.11.3) |
結果 |
AC
|
実行時間 | 292 ms / 2,000 ms |
コード長 | 2,982 bytes |
コンパイル時間 | 75 ms |
コンパイル使用メモリ | 11,324 KB |
実行使用メモリ | 29,760 KB |
最終ジャッジ日時 | 2023-09-16 07:26:47 |
合計ジャッジ時間 | 19,033 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 145 ms
29,460 KB |
testcase_01 | AC | 143 ms
29,532 KB |
testcase_02 | AC | 143 ms
29,580 KB |
testcase_03 | AC | 143 ms
29,604 KB |
testcase_04 | AC | 144 ms
29,476 KB |
testcase_05 | AC | 145 ms
29,596 KB |
testcase_06 | AC | 145 ms
29,352 KB |
testcase_07 | AC | 145 ms
29,396 KB |
testcase_08 | AC | 144 ms
29,372 KB |
testcase_09 | AC | 144 ms
29,632 KB |
testcase_10 | AC | 147 ms
29,680 KB |
testcase_11 | AC | 149 ms
29,620 KB |
testcase_12 | AC | 148 ms
29,380 KB |
testcase_13 | AC | 151 ms
29,392 KB |
testcase_14 | AC | 145 ms
29,664 KB |
testcase_15 | AC | 147 ms
29,648 KB |
testcase_16 | AC | 149 ms
29,448 KB |
testcase_17 | AC | 145 ms
29,668 KB |
testcase_18 | AC | 143 ms
29,656 KB |
testcase_19 | AC | 146 ms
29,656 KB |
testcase_20 | AC | 166 ms
29,656 KB |
testcase_21 | AC | 167 ms
29,672 KB |
testcase_22 | AC | 169 ms
29,460 KB |
testcase_23 | AC | 168 ms
29,688 KB |
testcase_24 | AC | 166 ms
29,524 KB |
testcase_25 | AC | 165 ms
29,672 KB |
testcase_26 | AC | 165 ms
29,528 KB |
testcase_27 | AC | 166 ms
29,572 KB |
testcase_28 | AC | 164 ms
29,444 KB |
testcase_29 | AC | 169 ms
29,564 KB |
testcase_30 | AC | 162 ms
29,696 KB |
testcase_31 | AC | 167 ms
29,560 KB |
testcase_32 | AC | 169 ms
29,756 KB |
testcase_33 | AC | 171 ms
29,760 KB |
testcase_34 | AC | 166 ms
29,668 KB |
testcase_35 | AC | 172 ms
29,680 KB |
testcase_36 | AC | 172 ms
29,532 KB |
testcase_37 | AC | 168 ms
29,500 KB |
testcase_38 | AC | 168 ms
29,524 KB |
testcase_39 | AC | 166 ms
29,696 KB |
testcase_40 | AC | 200 ms
29,692 KB |
testcase_41 | AC | 206 ms
29,704 KB |
testcase_42 | AC | 210 ms
29,660 KB |
testcase_43 | AC | 204 ms
29,460 KB |
testcase_44 | AC | 204 ms
29,572 KB |
testcase_45 | AC | 203 ms
29,704 KB |
testcase_46 | AC | 204 ms
29,572 KB |
testcase_47 | AC | 207 ms
29,756 KB |
testcase_48 | AC | 207 ms
29,564 KB |
testcase_49 | AC | 206 ms
29,712 KB |
testcase_50 | AC | 206 ms
29,688 KB |
testcase_51 | AC | 207 ms
29,528 KB |
testcase_52 | AC | 206 ms
29,640 KB |
testcase_53 | AC | 205 ms
29,748 KB |
testcase_54 | AC | 201 ms
29,712 KB |
testcase_55 | AC | 204 ms
29,640 KB |
testcase_56 | AC | 203 ms
29,420 KB |
testcase_57 | AC | 204 ms
29,708 KB |
testcase_58 | AC | 201 ms
29,532 KB |
testcase_59 | AC | 203 ms
29,436 KB |
testcase_60 | AC | 263 ms
29,560 KB |
testcase_61 | AC | 266 ms
29,440 KB |
testcase_62 | AC | 282 ms
29,648 KB |
testcase_63 | AC | 281 ms
29,744 KB |
testcase_64 | AC | 282 ms
29,760 KB |
testcase_65 | AC | 287 ms
29,536 KB |
testcase_66 | AC | 288 ms
29,600 KB |
testcase_67 | AC | 290 ms
29,472 KB |
testcase_68 | AC | 289 ms
29,648 KB |
testcase_69 | AC | 287 ms
29,708 KB |
testcase_70 | AC | 291 ms
29,488 KB |
testcase_71 | AC | 286 ms
29,644 KB |
testcase_72 | AC | 292 ms
29,748 KB |
testcase_73 | AC | 285 ms
29,652 KB |
testcase_74 | AC | 289 ms
29,716 KB |
testcase_75 | AC | 291 ms
29,528 KB |
testcase_76 | AC | 283 ms
29,512 KB |
testcase_77 | AC | 283 ms
29,548 KB |
testcase_78 | AC | 288 ms
29,692 KB |
testcase_79 | AC | 286 ms
29,532 KB |
ソースコード
import sys import numpy as np read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines # 頂点の代わりに辺を選ぶ MOD = 10**9 + 7 def compute_next_status(status, vertical): status = list(status) deg = [0] * 4 for i, x in enumerate(status): if x != 0: deg[i] = 1 loop = False for i in range(3): if vertical & (1 << i): deg[i] += 1 deg[i+1] += 1 if status[i] == status[i+1] != 0: if loop: return None loop = True status[i] = status[i+1] = 0 continue if status[i] == status[i+1] == 0: status[i] = status[i+1] = max(status) + 1 elif status[i] != 0 and status[i+1] == 0: status[i+1] = status[i] elif status[i+1] != 0 and status[i] == 0: status[i] = status[i+1] else: n, m = status[i:i+2] n, m = max(n, m), min(n, m) for v in range(4): if status[v] == m: status[v] = n if loop: if any(x in [1,3] for x in deg): return None return (0,0,0,0) if any(x >= 3 for x in deg): return None for v in range(4): if deg[v] != 1: status[v] = 0 for n, k in enumerate(set(status + [0])): if k == 0: continue for v in range(4): if status[v] == k: status[v] = n return tuple(status) visited = set([(0,0,0,0)]) q = [(0,0,0,0)] edges = [] # 遷移に加えて、追加した辺の本数を持たせる popcount = [0,1,1,2,1,2,2,3] while q: v = q.pop() for i in range(8): w = compute_next_status(v, i) if w is None: continue edges.append((v,w, popcount[i] + sum(x != 0 for x in w))) if w in visited: continue visited.add(w) q.append(w) L = len(visited) + 1 A = np.zeros((2*L,2*L), dtype=object) v_to_i = {v:i for i,v in enumerate(visited)} i0 = v_to_i[(0,0,0,0)] i_end = L - 1 for v,w,k in edges: iv, iw = v_to_i[v], v_to_i[w] if iv != i0 and iw == i0: iw = i_end A[2*iw, 2*iv] = 1 # 選択なし -> 選択なし A[2*iw+1, 2*iv] = k # 選択なし -> 選択あり A[2*iw+1,2*iv+1] = 1 # 選択あり -> 選択あり A[2*i_end, 2*i_end] += 1 A[2*i_end+1, 2*i_end+1] += 1 def mult_mod(A, B, MOD=MOD): mask = (1<<15) - 1 A1, A2 = A>>15, A & mask B1, B2 = B>>15, B&mask X = np.dot(A1, B1) % MOD Z = np.dot(A2, B2) % MOD Y = (np.dot(A1+A2,B1+B2)-X-Z)%MOD return ((X<<30)+(Y<<15)+Z)%MOD def matrix_power(A, n, MOD=MOD): if n == 1: return A B = matrix_power(A, n//2) B = mult_mod(B, B) if n & 1: B = mult_mod(A, B) return B N = int(read()) print(matrix_power(A, N + 1)[2*i_end+1, 2*i0])