結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー gew1fw
提出日時 2025-06-12 16:05:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,052 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 467,312 KB
最終ジャッジ日時 2025-06-12 16:06:00
合計ジャッジ時間 6,327 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N, K = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    m = []
    for i in range(N):
        exponent = N - 1 - i
        mi = pow(10, exponent, K)
        m.append(mi)
    
    dp = defaultdict(int)
    initial_counts = tuple([0] * 9)
    dp[(0, initial_counts)] = 1
    
    for i in range(N):
        next_dp = defaultdict(int)
        for (r, counts), ways in dp.items():
            for d in range(1, 10):
                idx = d - 1
                if counts[idx] < c[idx]:
                    new_counts = list(counts)
                    new_counts[idx] += 1
                    new_counts_tuple = tuple(new_counts)
                    contribution = d * m[i]
                    new_r = (r + contribution) % K
                    next_dp[(new_r, new_counts_tuple)] += ways
        dp = next_dp
    
    target_r = 0
    target_counts = tuple(c)
    print(dp.get((target_r, target_counts), 0))

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