結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
ユーザー lam6er
提出日時 2025-04-15 22:55:11
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,014 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 661,676 KB
最終ジャッジ日時 2025-04-15 22:56:54
合計ジャッジ時間 5,872 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 MLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations
from collections import defaultdict

def main():
    N, K = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    
    # Precompute the multipliers for each position
    multipliers = []
    for p in range(N):
        # For position p (0-based), the multiplier is 10^(N-1 - p) mod K
        exponent = N - 1 - p
        m = pow(10, exponent, K) if K != 0 else 10**exponent
        multipliers.append(m)
    
    # Check if K is larger than the maximum possible number (10^N - 1)
    max_num = 10**N - 1
    if K != 0 and K > max_num:
        print(0)
        return
    
    # Initialize DP: mask is the bitmask of used positions, remainder is the current sum mod K
    dp = defaultdict(int)
    dp[(0, 0)] = 1  # mask 0, remainder 0, count 1
    
    for digit in range(1, 10):
        cnt = c[digit - 1]
        if cnt == 0:
            continue
        
        new_dp = defaultdict(int)
        for (mask, rem), ways in dp.items():
            # Get available positions
            available = []
            for p in range(N):
                if not (mask & (1 << p)):
                    available.append(p)
            if len(available) < cnt:
                continue
            
            # Generate all possible subsets of size cnt
            for subset in combinations(available, cnt):
                subset_mask = 0
                sum_m = 0
                for p in subset:
                    subset_mask |= (1 << p)
                    sum_m += multipliers[p]
                sum_m %= K
                contribution = (digit * sum_m) % K
                new_rem = (rem + contribution) % K
                new_mask = mask | subset_mask
                new_dp[(new_mask, new_rem)] += ways
        
        dp = new_dp
    
    # The answer is the count of full mask (all positions used) with remainder 0
    full_mask = (1 << N) - 1
    print(dp.get((full_mask, 0), 0))

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