結果

問題 No.3566 Subsequence Sum
コンテスト
ユーザー 👑 to-omer
提出日時 2023-07-13 01:26:23
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 381 ms / 2,000 ms
コード長 982 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,757 ms
コンパイル使用メモリ 84,864 KB
実行使用メモリ 126,604 KB
最終ジャッジ日時 2026-06-05 20:50:46
合計ジャッジ時間 4,233 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353


def matmul(A, B):
    N = len(A)
    M = len(A[0])
    assert M == len(B)
    L = len(B[0])
    C = [[0 for _ in range(L)] for _ in range(N)]
    for i in range(N):
        for j in range(L):
            for k in range(M):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C


def main():
    N = list(map(int, input()))
    K = int(input())
    M = [[int(i == j) for j in range(23)] for i in range(23)]
    for i in range(23):
        A = M[i]
        for n in N:
            y = (A[21] + (A[22] if n else 0)) % MOD
            x = (A[20] * 10 + y * n) % MOD
            A[20] = (A[20] + x - A[n * 2]) % MOD
            A[21] = (A[21] + y - A[n * 2 + 1]) % MOD
            A[n * 2] = x
            A[n * 2 + 1] = y

    P = [[int(i == j) for j in range(23)] for i in range(23)]
    while K:
        if K & 1:
            P = matmul(P, M)
        M = matmul(M, M)
        K >>= 1
    print(P[22][20])


if __name__ == "__main__":
    main()
0