結果
問題 | No.579 3 x N グリッド上のサイクルのサイズ(hard) |
ユーザー |
![]() |
提出日時 | 2020-05-06 18:23:41 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 684 ms / 2,000 ms |
コード長 | 2,982 bytes |
コンパイル時間 | 94 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 44,948 KB |
最終ジャッジ日時 | 2024-07-03 09:05:39 |
合計ジャッジ時間 | 44,679 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 80 |
ソースコード
import sysimport numpy as npread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlines# 頂点の代わりに辺を選ぶMOD = 10**9 + 7def compute_next_status(status, vertical):status = list(status)deg = [0] * 4for i, x in enumerate(status):if x != 0:deg[i] = 1loop = Falsefor i in range(3):if vertical & (1 << i):deg[i] += 1deg[i+1] += 1if status[i] == status[i+1] != 0:if loop:return Noneloop = Truestatus[i] = status[i+1] = 0continueif status[i] == status[i+1] == 0:status[i] = status[i+1] = max(status) + 1elif 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] = nif loop:if any(x in [1,3] for x in deg):return Nonereturn (0,0,0,0)if any(x >= 3 for x in deg):return Nonefor v in range(4):if deg[v] != 1:status[v] = 0for n, k in enumerate(set(status + [0])):if k == 0:continuefor v in range(4):if status[v] == k:status[v] = nreturn 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:continueedges.append((v,w, popcount[i] + sum(x != 0 for x in w)))if w in visited:continuevisited.add(w)q.append(w)L = len(visited) + 1A = 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 - 1for v,w,k in edges:iv, iw = v_to_i[v], v_to_i[w]if iv != i0 and iw == i0:iw = i_endA[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] += 1A[2*i_end+1, 2*i_end+1] += 1def mult_mod(A, B, MOD=MOD):mask = (1<<15) - 1A1, A2 = A>>15, A & maskB1, B2 = B>>15, B&maskX = np.dot(A1, B1) % MODZ = np.dot(A2, B2) % MODY = (np.dot(A1+A2,B1+B2)-X-Z)%MODreturn ((X<<30)+(Y<<15)+Z)%MODdef matrix_power(A, n, MOD=MOD):if n == 1:return AB = matrix_power(A, n//2)B = mult_mod(B, B)if n & 1:B = mult_mod(A, B)return BN = int(read())print(matrix_power(A, N + 1)[2*i_end+1, 2*i0])