結果

問題 No.3202 Periodic Alternating Subsequence
ユーザー tassei903
提出日時 2025-07-12 13:56:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,274 ms / 2,000 ms
コード長 2,225 bytes
コンパイル時間 457 ms
コンパイル使用メモリ 81,952 KB
実行使用メモリ 77,172 KB
最終ジャッジ日時 2025-07-12 13:56:47
合計ジャッジ時間 27,321 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
#2D matrix
mod = 10 ** 9 + 7

def mat_add(A, B):
    assert len(A)==len(B) and len(A[0]) == len(B[0])
    n = len(A)
    m = len(A[0])
    for i in range(n):
        for j in range(m):
            A[i][j] += B[i][j]
            A[i][j] %= mod
    return A


def mat_mul(A,B):
    assert len(A[0]) == len(B)
    n = len(A)
    m = len(B[0])
    p = len(A[0])
    R = [[0 for j in range(m)]for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(p):
                R[i][j] += A[i][k]*B[k][j] % mod
                R[i][j] %= mod
    return R

def mat_pow(A, x):
    assert len(A)==len(A[0])
    n = len(A)
    R = [[0 for j in range(n)]for i in range(n)]
    for i in range(n):
        R[i][i] = 1
    while x > 0:
        if x&1:
            R = mat_mul(R, A)
        A = mat_mul(A,A)
        x >>= 1
    return R

def mat_pri(A):
    for i in A:
        print(*i)


t = input()
k = ni()

M = 7

S = [[0] * M for i in range(M)]

for i in range(M):

    S[i][i] = 1

A = [[1, 1, 0, 1, 0, 0, 0], 
     [0, 1, 0, 0, 0, 0, 0],
     [0, 1, 1, 1, 0, 0, 0],
     [0, 0, 0, 1, 0, 0, 0],
     [0, 0, 0, 1, 1, 1, 0],
     [0, 0, 0, 0, 0, 1, 0],
     [0, 0, 0, 0, 0, 1, 1]]

B = [[1, 0, 1, 0, 1, 0, 0], 
     [0, 1, 1, 0, 1, 0, 0],
     [0, 0, 1, 0, 0, 0, 0],
     [0, 0, 0, 1, 1, 0, 1],
     [0, 0, 0, 0, 1, 0, 0],
     [0, 0, 0, 0, 0, 1, 1],
     [0, 0, 0, 0, 0, 0, 1]]

for i in range(len(t)):
    if t[i] == "0":
        S = mat_mul(S, A)
    else:
        S = mat_mul(S, B)

S = mat_pow(S, k)
# print(S)
v = [[1, 0, 0, 0, 0, 0, 0]]
v = mat_mul(v, S)
# print(v)
ans = v[0][3] + v[0][4] + v[0][5] * 2 + v[0][6]  * 2
print(ans % mod)

# v = [[1, 0, 0, 0, 0, 0, 0]]
# for _ in range(k):
#     for i in range(len(t)):
#         if t[i] == "0":
#             v = mat_mul(v, A)
#         else:
#             v = mat_mul(v, B)
#         print(v)
0