結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:19:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 857 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 331,668 KB
最終ジャッジ日時 2025-04-16 16:21:06
合計ジャッジ時間 5,695 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

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

# Convert c to a tuple for use as a key in the DP dictionary
c_tuple = tuple(c)

# Initialize DP with the initial state: no digits used, remainder 0
dp = defaultdict(int)
initial_used = tuple([0] * 9)
dp[(initial_used, 0)] = 1

for _ in range(n):
    next_dp = defaultdict(int)
    for (used, rem), cnt in dp.items():
        for d in range(9):
            if used[d] < c[d]:
                new_used = list(used)
                new_used[d] += 1
                new_used_tuple = tuple(new_used)
                new_rem = (rem * 10 + (d + 1)) % k
                next_dp[(new_used_tuple, new_rem)] += cnt
    dp = next_dp

# The answer is the count of states where all digits are used and remainder is 0
answer = dp.get((c_tuple, 0), 0)
print(answer)
0