結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
ユーザー gew1fw
提出日時 2025-06-12 20:57:19
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,029 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 751,108 KB
最終ジャッジ日時 2025-06-12 21:00:59
合計ジャッジ時間 7,069 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 MLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    # Precompute 10^i mod K for i in 0..N-1
    e = [1] * N
    for i in range(1, N):
        e[i] = (e[i-1] * 10) % K

    # We'll represent the counts as a tuple
    initial_counts = tuple(c)

    @lru_cache(maxsize=None)
    def dp(pos, rem, counts):
        if pos == N:
            return 1 if rem == 0 else 0
        total = 0
        for d in range(9):
            if counts[d] == 0:
                continue
            new_counts = list(counts)
            new_counts[d] -= 1
            new_counts = tuple(new_counts)
            contribution = (d + 1) * e[pos]  # since d starts from 0 to 8, digits are 1-9
            new_rem = (rem + contribution) % K
            total += dp(pos + 1, new_rem, new_counts)
        return total

    result = dp(0, 0, initial_counts)
    print(result)

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