結果

問題 No.3202 Periodic Alternating Subsequence
コンテスト
ユーザー YY-otter
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0