結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
ユーザー lam6er
提出日時 2025-04-15 22:50:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 979 bytes
コンパイル時間 426 ms
コンパイル使用メモリ 81,956 KB
実行使用メモリ 692,496 KB
最終ジャッジ日時 2025-04-15 22:52:41
合計ジャッジ時間 6,674 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 WA * 2 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()))
    
    e = []
    for i in range(N):
        exponent = N - 1 - i
        e_i = pow(10, exponent, K)
        e.append(e_i)
    
    sum_e = sum(e)
    S_max = 9 * sum_e
    
    if K > S_max:
        print(0)
        return
    
    c_tuple = tuple(c)
    
    @lru_cache(maxsize=None)
    def dfs(rem, pos, *counts):
        if pos == N:
            return 1 if rem % K == 0 else 0
        
        res = 0
        for d in range(9):
            if counts[d] == 0:
                continue
            new_counts = list(counts)
            new_counts[d] -= 1
            contribution = (d + 1) * e[pos]
            new_rem = (rem + contribution) % K
            res += dfs(new_rem, pos + 1, *new_counts)
        return res
    
    result = dfs(0, 0, *c_tuple)
    print(result)

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