結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:51:30
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,205 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,624 KB
実行使用メモリ 599,760 KB
最終ジャッジ日時 2025-06-12 15:51:41
合計ジャッジ時間 7,526 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())
    counts = list(map(int, sys.stdin.readline().split()))
    
    # Precompute the digits that are available and their counts
    digits = [(i+1, counts[i]) for i in range(9) if counts[i] > 0]
    
    # Convert counts into a tuple for easier handling
    initial_counts = tuple(counts)
    
    @lru_cache(maxsize=None)
    def dp(current_counts, rem):
        # Check if all counts are zero (base case)
        if all(c == 0 for c in current_counts):
            return 1 if rem == 0 else 0
        
        total = 0
        for i in range(9):
            if current_counts[i] == 0:
                continue
            # Create new counts by decrementing the ith digit
            new_counts = list(current_counts)
            new_counts[i] -= 1
            new_counts_tuple = tuple(new_counts)
            # Compute the new remainder
            new_rem = (rem * 10 + (i + 1)) % k
            total += dp(new_counts_tuple, new_rem)
        
        return total
    
    result = dp(initial_counts, 0)
    print(result)

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