結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:32:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,485 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 119,272 KB
最終ジャッジ日時 2025-03-20 20:33:02
合計ジャッジ時間 6,540 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
from collections import defaultdict

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

# Calculate the product of factorials of the counts
product_factorial = 1
for count in c:
    product_factorial *= math.factorial(count)

# Special case: K=1, all numbers are divisible by 1
if k == 1:
    total = math.factorial(n) // product_factorial
    print(total)
    exit()

# Initialize dynamic programming
dp = defaultdict(lambda: defaultdict(int))
initial_remaining = tuple(c)
dp[initial_remaining][0] = 1

for _ in range(n):
    new_dp = defaultdict(lambda: defaultdict(int))
    for remaining in list(dp.keys()):
        rem_dict = dp[remaining]
        for current_rem, count in rem_dict.items():
            for digit in range(1, 10):
                idx = digit - 1
                if remaining[idx] == 0:
                    continue
                # Calculate new remaining counts after using this digit
                new_remaining = list(remaining)
                new_remaining[idx] -= 1
                new_remaining = tuple(new_remaining)
                # Calculate new remainder
                new_rem = (current_rem * 10 + digit) % k
                # Update the new_dp with multiplied by the available count
                new_dp[new_remaining][new_rem] += count * remaining[idx]
    dp = new_dp

# Extract the final answer
final_remaining = tuple([0]*9)
answer = dp.get(final_remaining, {}).get(0, 0) // product_factorial

print(answer)
0