結果
問題 |
No.3202 Periodic Alternating Subsequence
|
ユーザー |
|
提出日時 | 2025-06-27 05:05:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 960 ms / 2,000 ms |
コード長 | 2,528 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 77,000 KB |
最終ジャッジ日時 | 2025-07-06 03:57:59 |
合計ジャッジ時間 | 20,531 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
import sys def solve(): """ DPと行列累乗を用いて問題を解くメイン関数 """ T = sys.stdin.readline().strip() K = int(sys.stdin.readline().strip()) MOD = 1000000007 DIM = 7 # 行列の次元 (C0, L0, Q0, C1, L1, Q1, 1) def mat_mul(A, B, mod): """2つの DIM x DIM 行列の積を計算する""" C = [[0] * DIM for _ in range(DIM)] for i in range(DIM): for j in range(DIM): for l in range(DIM): C[i][j] += A[i][l] * B[l][j] C[i][j] %= mod return C def mat_pow(A, k, mod): """行列Aのk乗を繰り返し二乗法で計算する""" # 単位行列 res = [[0] * DIM for _ in range(DIM)] for i in range(DIM): res[i][i] = 1 base = A while k > 0: if k & 1: res = mat_mul(res, base, mod) base = mat_mul(base, base, mod) k >>= 1 return res # S[i] = '0' のときの遷移行列 # V_i = M0 * V_{i-1} # V = (C0, L0, Q0, C1, L1, Q1, 1)^T M0 = [ [1, 0, 0, 1, 0, 0, 1], # C0' = C0 + C1 + 1 [0, 1, 0, 1, 1, 0, 1], # L0' = L0 + L1 + C1 + 1 [0, 0, 1, 1, 2, 1, 1], # Q0' = Q0 + Q1 + 2L1 + C1 + 1 [0, 0, 0, 1, 0, 0, 0], # C1' = C1 [0, 0, 0, 0, 1, 0, 0], # L1' = L1 [0, 0, 0, 0, 0, 1, 0], # Q1' = Q1 [0, 0, 0, 0, 0, 0, 1] ] # S[i] = '1' のときの遷移行列 M1 = [ [1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 1], [1, 1, 0, 0, 1, 0, 1], [1, 2, 1, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0, 1] ] # 文字列T全体に対する遷移行列M_Tを計算 # M_T = M_{T[-1]} * ... * M_{T[0]} M_T = [[0] * DIM for _ in range(DIM)] for i in range(DIM): M_T[i][i] = 1 # 単位行列で初期化 for char in T: if char == '0': M_T = mat_mul(M0, M_T, MOD) else: # char == '1' M_T = mat_mul(M1, M_T, MOD) # M_TをK乗して、S全体に対する遷移行列を求める M_final = mat_pow(M_T, K, MOD) # 最終的なスコアの総和は、M_finalの最後の列の # Q0成分とQ1成分の和になる # V_final = M_final * (0,0,0,0,0,0,1)^T final_q0 = M_final[2][6] final_q1 = M_final[5][6] result = (final_q0 + final_q1) % MOD print(result) if __name__ == "__main__": solve()