結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:18:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 942 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 81,460 KB
実行使用メモリ 466,888 KB
最終ジャッジ日時 2025-04-15 23:20:09
合計ジャッジ時間 6,050 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

n, k = map(int, input().split())
c = list(map(int, input().split()))

if k == 0:
    print(0)
    exit()

pow10 = [pow(10, (n - 1 - m), k) for m in range(n)]

# Initialize DP with initial state: all counts 0, remainder 0
dp = defaultdict(int)
initial_counts = tuple([0] * 9)
dp[(initial_counts, 0)] = 1

for m in range(n):
    next_dp = defaultdict(int)
    for (counts, rem), cnt in dp.items():
        for d in range(9):
            if counts[d] < c[d]:
                new_counts = list(counts)
                new_counts[d] += 1
                new_counts_tuple = tuple(new_counts)
                contribution = (d + 1) * pow10[m]
                new_rem = (rem + contribution) % k
                next_dp[(new_counts_tuple, new_rem)] += cnt
    dp = next_dp

# Sum all states where remainder is 0
result = 0
for (counts, rem), cnt in dp.items():
    if rem == 0:
        result += cnt

print(result)
0