結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
ユーザー gew1fw
提出日時 2025-06-12 18:15:33
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,095 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 849,160 KB
最終ジャッジ日時 2025-06-12 18:16:30
合計ジャッジ時間 10,481 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 MLE * 2 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    n, k = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    c = c  # c[0] is count of digit 1, ..., c[8] is count of digit 9

    if k == 1:
        # All numbers are divisible by 1
        total = 1
        for cnt in c:
            if cnt > 0:
                total *= 1
        # Compute the number of permutations
        numerator = 1
        for i in range(1, n+1):
            numerator *= i
        denominator = 1
        for cnt in c:
            for i in range(1, cnt+1):
                denominator *= i
        print(numerator // denominator)
        return

    # Precompute 10^{(n-1 - p} mod k for each position p (0-based from left to right)
    pow10_mod = [pow(10, (n-1 - p), k) % k for p in range(n)]

    # Split positions into two halves
    half = (n + 1) // 2
    first_half_positions = list(range(half))
    second_half_positions = list(range(half, n))

    def generate_combinations(positions, c, pow10_mod):
        counts_dict = defaultdict(int)
        m = len(positions)
        # Convert c to a tuple for easier handling
        def backtrack(pos_idx, current_sum, counts):
            if pos_idx == m:
                mod_sum = current_sum % k
                counts_tuple = tuple(counts)
                counts_dict[(mod_sum, counts_tuple)] += 1
                return
            # Current global position is positions[pos_idx]
            p = positions[pos_idx]
            for d in range(1, 10):
                if counts[d-1] < c[d-1]:
                    new_counts = list(counts)
                    new_counts[d-1] += 1
                    contribution = (d * pow10_mod[p]) % k
                    new_sum = (current_sum + contribution) % k
                    backtrack(pos_idx + 1, new_sum, new_counts)
        initial_counts = [0]*9
        backtrack(0, 0, initial_counts)
        return counts_dict

    # Generate combinations for both halves
    first_half_comb = generate_combinations(first_half_positions, c, pow10_mod)
    second_half_comb = generate_combinations(second_half_positions, c, pow10_mod)

    # Preprocess second_half_comb into a dictionary grouped by sum_b
    second_half_grouped = defaultdict(list)
    for (sum_b, counts_b), cnt in second_half_comb.items():
        second_half_grouped[sum_b].append( (counts_b, cnt) )

    total = 0
    # Iterate through all entries in the first half
    for (sum_a, counts_a), cnt_a in first_half_comb.items():
        required_sum_b = (-sum_a) % k
        # Look up in second_half_grouped
        if required_sum_b not in second_half_grouped:
            continue
        # Check all entries in second_half_grouped[required_sum_b]
        for (counts_b, cnt_b) in second_half_grouped[required_sum_b]:
            valid = True
            for i in range(9):
                if counts_a[i] + counts_b[i] > c[i]:
                    valid = False
                    break
            if valid:
                total += cnt_a * cnt_b
    print(total)

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