結果

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

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

def main():
    N, K = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    if sum(c) != N:
        print(0)
        return
    
    # Precompute factorials up to N
    max_n = N
    factorial = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        factorial[i] = factorial[i-1] * i
    
    # Compute initial multinomial coefficient
    initial_counts = tuple(c)
    sum_counts = sum(initial_counts)
    denominator = 1
    for count in initial_counts:
        if count > 0:
            denominator *= factorial[count]
    multinom = factorial[sum_counts] // denominator
    
    # Initialize DP
    dp = defaultdict(int)
    dp[(initial_counts, 0)] = multinom
    
    for _ in range(N):
        new_dp = defaultdict(int)
        for (counts, r), ways in dp.items():
            s = sum(counts)
            if s == 0:
                continue
            for d in range(9):
                if counts[d] == 0:
                    continue
                new_counts = list(counts)
                new_counts[d] -= 1
                new_counts_tuple = tuple(new_counts)
                digit = d + 1
                new_r = (r * 10 + digit) % K
                new_ways = ways * counts[d] // s
                new_dp[(new_counts_tuple, new_r)] += new_ways
        dp = new_dp
    
    zero_counts = tuple([0] * 9)
    print(dp.get((zero_counts, 0), 0))

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