結果

問題 No.1783 Remix Sum
ユーザー gew1fw
提出日時 2025-06-12 20:27:40
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,969 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 844,248 KB
最終ジャッジ日時 2025-06-12 20:28:00
合計ジャッジ時間 3,234 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other MLE * 1 -- * 75
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 120586241

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx +=1
    K = int(data[idx]); idx +=1
    M = int(data[idx]); idx +=1
    T = int(data[idx]); idx +=1
    
    a = list(map(int, data[idx:idx+N]))
    a = [x % (10**K) for x in a]
    
    size = 10**K
    trans = [[0]*size for _ in range(size)]
    
    for num in a:
        s = [0]*K
        for i in range(K):
            s[i] = (num // (10**i)) % 10
        
        for x in range(size):
            allowed = True
            for i in range(T):
                xi = (x // (10**i)) % 10
                yi = s[i]
                if xi + yi >= 10:
                    allowed = False
                    break
            if not allowed:
                continue
            
            z = 0
            for i in range(K):
                xi = (x // (10**i)) % 10
                yi = s[i]
                if i < T:
                    zi = xi + yi
                else:
                    zi = (xi + yi) % 10
                z += zi * (10**i)
            trans[x][z] += 1
    
    def mat_mult(A, B):
        res = [[0]*size for _ in range(size)]
        for i in range(size):
            for k in range(size):
                if A[i][k] == 0:
                    continue
                for j in range(size):
                    res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % MOD
        return res
    
    def mat_pow(mat, power):
        result = [[0]*size for _ in range(size)]
        for i in range(size):
            result[i][i] = 1
        
        while power > 0:
            if power % 2 == 1:
                result = mat_mult(result, mat)
            mat = mat_mult(mat, mat)
            power //= 2
        return result
    
    mat = [row[:] for row in trans]
    mat = mat_pow(mat, M)
    
    for i in range(size):
        print(mat[0][i] % MOD)
    
if __name__ == "__main__":
    main()
0