結果

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

ソースコード

diff # 

import sys
from math import factorial
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    c = list(map(int, input[idx:idx+9]))
    idx += 9
    
    if K == 1:
        total = factorial(N)
        for ci in c:
            total //= factorial(ci)
        print(total)
        return
    
    counts_initial = tuple(c)
    dp = defaultdict(int)
    initial_remainder = 0
    dp[(initial_remainder, counts_initial)] = 1
    
    for _ in range(N):
        next_dp = defaultdict(int)
        for (r, counts), ways in dp.items():
            for d in range(1, 10):
                if counts[d-1] == 0:
                    continue
                new_counts = list(counts)
                new_counts[d-1] -= 1
                new_counts_tuple = tuple(new_counts)
                new_r = (r * 10 + d) % K
                next_dp[(new_r, new_counts_tuple)] += ways
        dp = next_dp
    
    all_zero = tuple([0]*9)
    print(dp.get((0, all_zero), 0))

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