結果

問題 No.3202 Periodic Alternating Subsequence
ユーザー kidodesu
提出日時 2025-07-11 23:05:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 775 ms / 2,000 ms
コード長 1,572 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 109,316 KB
最終ジャッジ日時 2025-07-11 23:06:21
合計ジャッジ時間 16,587 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

t = input()
k = int(input())
mod = 10 ** 9 + 7

dp = [[0, 0, 0], [0, 0, 1], [0, 0, 1], [0, 0, 0]] 
from copy import deepcopy as cp
for i in range(len(t)):
    ndp = cp(dp)
    a = int(t[i])
    for j in range(4):
        if j & 1 != a:
            ndp[j^1][0] += dp[j][0] + 2 * dp[j][1] + dp[j][2]; ndp[j^1][0] %= mod
            ndp[j^1][1] += dp[j][1] + dp[j][2]; ndp[j^1][1] %= mod
            ndp[j^1][2] += dp[j][2]; ndp[j^1][2] %= mod
    dp = ndp

B = dp
ans = [[0, 0, 0], [0, 0, 1], [0, 0, 1], [0, 0, 0]] 
while k:
    if k & 1:
        ndp = [[0, 0, 0] for _ in range(4)]
        for i in range(4):
            for j in range(4):
                if i & 1 != (j >> 1) & 1:
                    nxt = (i & 2) | (j & 1)
                    ndp[nxt][0] += ans[i][0] * B[j][2] + ans[i][2] * B[j][0] + 2 * ans[i][1] * B[j][1]; ndp[nxt][0] %= mod
                    ndp[nxt][1] += ans[i][1] * B[j][2] + ans[i][2] * B[j][1]; ans[nxt][1] %= mod
                    ndp[nxt][2] += ans[i][2] * B[j][2]; ndp[nxt][2] %= mod
        ans = ndp
    ndp = [[0, 0, 0] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            if i & 1 != (j >> 1) & 1:
                nxt = (i & 2) | (j & 1)
                ndp[nxt][0] += B[i][0] * B[j][2] + B[i][2] * B[j][0] + 2 * B[i][1] * B[j][1]; ndp[nxt][0] %= mod
                ndp[nxt][1] += B[i][1] * B[j][2] + B[i][2] * B[j][1]; ndp[nxt][1] %= mod
                ndp[nxt][2] += B[i][2] * B[j][2]; ndp[nxt][2] %= mod
    B = ndp
    k >>= 1

Ans = 0
for i in range(4):
    Ans += ans[i][0]; Ans %= mod
print(Ans)
0