結果

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

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    N, K = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    
    # Precompute the exponents for each position
    exponents = []
    for j in range(N):
        exponents.append(pow(10, N-1 - j, K))
    
    # Convert counts to a tuple for memoization
    counts = tuple(c)
    
    @lru_cache(maxsize=None)
    def backtrack(pos, current_mod, cnt):
        if pos == N:
            return 1 if current_mod == 0 else 0
        res = 0
        for d in range(9):
            if cnt[d] == 0:
                continue
            # Calculate the new counts after using this digit
            new_cnt = list(cnt)
            new_cnt[d] -= 1
            new_cnt = tuple(new_cnt)
            # Calculate the new mod value
            contribution = (d + 1) * exponents[pos]
            new_mod = (current_mod + contribution) % K
            res += backtrack(pos + 1, new_mod, new_cnt)
        return res
    
    total = backtrack(0, 0, counts)
    print(total)

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