結果

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

ソースコード

diff #
raw source code 

import sys
import math
from collections import defaultdict

def main():
    N, K = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    
    product_fact = 1
    for count in c:
        product_fact *= math.factorial(count)
    
    initial_counts = tuple(c)
    dp = defaultdict(int)
    dp[(initial_counts, 0)] = 1
    
    for _ in range(N):
        next_dp = defaultdict(int)
        for (counts, rem), cnt in dp.items():
            for i in range(9):
                if counts[i] > 0:
                    new_counts = list(counts)
                    new_counts[i] -= 1
                    new_counts_tuple = tuple(new_counts)
                    digit = i + 1
                    new_rem = (rem * 10 + digit) % K
                    next_dp[(new_counts_tuple, new_rem)] += cnt * counts[i]
        dp = next_dp
    
    sum_answer = 0
    for (counts, rem), cnt in dp.items():
        if all(x == 0 for x in counts) and rem == 0:
            sum_answer += cnt
    
    print(sum_answer // product_fact)

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