結果

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

ソースコード

diff #
raw source code 

from collections import defaultdict

def main():
    import sys
    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
    
    counts = tuple(c)
    
    current_dp = defaultdict(int)
    current_dp[(counts, 0)] = 1
    
    for _ in range(N):
        next_dp = defaultdict(int)
        for (cnt, rem), val in current_dp.items():
            for i in range(9):
                if cnt[i] > 0:
                    new_cnt = list(cnt)
                    new_cnt[i] -= 1
                    new_cnt_tuple = tuple(new_cnt)
                    digit = i + 1
                    new_rem = (rem * 10 + digit) % K
                    next_dp[(new_cnt_tuple, new_rem)] += val
        current_dp = next_dp
    
    all_zero_counts = tuple([0]*9)
    print(current_dp.get((all_zero_counts, 0), 0))

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