結果

問題 No.3310 mod998
コンテスト
ユーザー detteiuu
提出日時 2025-10-24 22:49:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,047 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 209,532 KB
最終ジャッジ日時 2025-10-24 22:50:17
合計ジャッジ時間 29,257 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998

def matrix(a, b):
    ans = [[0]*len(b[0]) for _ in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            ans[i][j] = sum(a[i][k]*b[k][j]%MOD for k in range(len(b)))%MOD
    return ans

for _ in range(int(input())):
    N, M = map(int, input().split())
    K = [input() for _ in range(M)]

    maxL = max(len(k) for k in K)
    dp = [N]
    dpN = []
    n = N
    for i in range(maxL-1):
        dp.append(dp[-1])
        dpN.append(n)
        for _ in range(9):
            dp[-1] = (dp[-1]*n%MOD+dp[-2])%MOD
        a = n
        for _ in range(9):
            n *= a
            n %= MOD
    dpN.append(n)
    
    for q in K:
        ans = 0
        for i, n in enumerate(q):
            n = int(n)
            idx = len(q)-1-i
            ans *= pow(dpN[idx], n, MOD)
            ans %= MOD
            SUM = 0
            for _ in range(n):
                SUM = (SUM*dpN[idx]%MOD+dp[idx])%MOD
            ans += SUM
            ans %= MOD
        ans += 1
        ans %= MOD
        print(ans)
0