結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー gew1fw
提出日時 2025-06-12 16:04:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,140 bytes
コンパイル時間 383 ms
コンパイル使用メモリ 82,760 KB
実行使用メモリ 356,384 KB
最終ジャッジ日時 2025-06-12 16:04:55
合計ジャッジ時間 6,471 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def solve():
    N, K = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    # Ensure c has exactly 9 elements
    while len(c) < 9:
        c.append(0)
    
    if K == 0:
        print(0)
        return
    
    # Precompute 10^{N-1 - pos} mod K for each pos
    pow10 = [1] * N
    for i in range(1, N):
        pow10[i] = (pow10[i-1] * 10) % K
    # Reverse to make pow10[pos] = 10^{N-1 - pos} mod K
    pow10 = pow10[::-1]
    
    @lru_cache(maxsize=None)
    def dfs(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
            digit = d + 1
            new_rem = (rem + digit * pow10[pos]) % K
            new_counts = list(counts)
            new_counts[d] -= 1
            new_counts = tuple(new_counts)
            total += dfs(pos + 1, new_rem, new_counts)
        return total
    
    initial_counts = tuple(c)
    result = dfs(0, 0, initial_counts)
    print(result)

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