結果
問題 |
No.1634 Sorting Integers (Multiple of K) Hard
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:07:47 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,014 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 81,220 KB |
実行使用メモリ | 137,580 KB |
最終ジャッジ日時 | 2025-04-16 16:15:02 |
合計ジャッジ時間 | 6,562 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 4 TLE * 1 -- * 23 |
ソースコード
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()