結果
問題 | No.541 3 x N グリッド上のサイクルの個数 |
ユーザー | maspy |
提出日時 | 2020-05-06 18:08:01 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 2,647 bytes |
コンパイル時間 | 79 ms |
コンパイル使用メモリ | 11,132 KB |
実行使用メモリ | 29,816 KB |
最終ジャッジ日時 | 2023-09-16 07:25:30 |
合計ジャッジ時間 | 11,913 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 134 ms
29,624 KB |
testcase_01 | AC | 134 ms
29,624 KB |
testcase_02 | AC | 135 ms
29,592 KB |
testcase_03 | AC | 134 ms
29,708 KB |
testcase_04 | AC | 134 ms
29,732 KB |
testcase_05 | AC | 135 ms
29,540 KB |
testcase_06 | AC | 135 ms
29,632 KB |
testcase_07 | AC | 135 ms
29,584 KB |
testcase_08 | AC | 137 ms
29,556 KB |
testcase_09 | AC | 146 ms
29,564 KB |
testcase_10 | AC | 149 ms
29,584 KB |
testcase_11 | AC | 150 ms
29,592 KB |
testcase_12 | AC | 149 ms
29,664 KB |
testcase_13 | AC | 149 ms
29,712 KB |
testcase_14 | AC | 151 ms
29,728 KB |
testcase_15 | AC | 150 ms
29,616 KB |
testcase_16 | AC | 149 ms
29,608 KB |
testcase_17 | AC | 149 ms
29,728 KB |
testcase_18 | AC | 147 ms
29,552 KB |
testcase_19 | AC | 159 ms
29,612 KB |
testcase_20 | AC | 159 ms
29,660 KB |
testcase_21 | AC | 165 ms
29,684 KB |
testcase_22 | AC | 164 ms
29,692 KB |
testcase_23 | AC | 167 ms
29,816 KB |
testcase_24 | AC | 163 ms
29,600 KB |
testcase_25 | AC | 166 ms
29,592 KB |
testcase_26 | AC | 165 ms
29,588 KB |
testcase_27 | AC | 166 ms
29,648 KB |
testcase_28 | AC | 162 ms
29,692 KB |
testcase_29 | AC | 137 ms
29,584 KB |
testcase_30 | AC | 138 ms
29,608 KB |
testcase_31 | AC | 137 ms
29,668 KB |
testcase_32 | AC | 138 ms
29,544 KB |
testcase_33 | AC | 138 ms
29,624 KB |
testcase_34 | AC | 136 ms
29,564 KB |
testcase_35 | AC | 136 ms
29,644 KB |
testcase_36 | AC | 136 ms
29,732 KB |
testcase_37 | AC | 136 ms
29,560 KB |
testcase_38 | AC | 138 ms
29,724 KB |
testcase_39 | AC | 139 ms
29,588 KB |
testcase_40 | AC | 150 ms
29,684 KB |
testcase_41 | AC | 149 ms
29,640 KB |
testcase_42 | AC | 148 ms
29,708 KB |
testcase_43 | AC | 146 ms
29,580 KB |
testcase_44 | AC | 149 ms
29,568 KB |
testcase_45 | AC | 148 ms
29,532 KB |
testcase_46 | AC | 147 ms
29,676 KB |
testcase_47 | AC | 148 ms
29,552 KB |
testcase_48 | AC | 153 ms
29,512 KB |
testcase_49 | AC | 151 ms
29,564 KB |
testcase_50 | AC | 154 ms
29,568 KB |
testcase_51 | AC | 168 ms
29,676 KB |
testcase_52 | AC | 165 ms
29,564 KB |
testcase_53 | AC | 165 ms
29,568 KB |
testcase_54 | AC | 165 ms
29,584 KB |
testcase_55 | AC | 163 ms
29,568 KB |
testcase_56 | AC | 165 ms
29,736 KB |
testcase_57 | AC | 163 ms
29,552 KB |
testcase_58 | AC | 165 ms
29,588 KB |
testcase_59 | AC | 165 ms
29,608 KB |
testcase_60 | AC | 170 ms
29,584 KB |
testcase_61 | AC | 168 ms
29,736 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 = [] 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)) if w in visited: continue visited.add(w) q.append(w) visited L = len(visited) + 1 A = np.zeros((L,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 in edges: iv, iw = v_to_i[v], v_to_i[w] if iv != i0 and iw == i0: iw = i_end A[iw, iv] = 1 A[i_end, i_end] += 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 MOD = 10**9 + 7 N = int(read()) print(matrix_power(A, N + 1)[i_end, i0])