結果
| 問題 |
No.1634 Sorting Integers (Multiple of K) Hard
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:55:47 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,624 ms / 3,000 ms |
| コード長 | 11,953 bytes |
| コンパイル時間 | 1,582 ms |
| コンパイル使用メモリ | 94,624 KB |
| 実行使用メモリ | 174,720 KB |
| 最終ジャッジ日時 | 2025-05-14 12:57:21 |
| 合計ジャッジ時間 | 26,490 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 28 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <array>
#include <vector> // Needed for factorial calculation in K=1 case
// Use std::array for map keys representing digit counts. It's fixed size and suitable for map keys.
// Size 10: Index 0 is unused, indices 1-9 store counts for digits 1-9.
using CountsArray = std::array<int, 10>;
long long N; // Total number of digits
long long K; // The divisor
CountsArray initial_counts; // Stores initial counts of digits 1-9
// Modular exponentiation: computes (base^exp) % K efficiently.
long long power(long long base, long long exp) {
long long res = 1;
// Special case: if K is 1, any number mod 1 is 0.
if (K == 1) return 0;
base %= K; // Initial reduction of base modulo K
while (exp > 0) {
// If exp is odd, multiply res with base
if (exp % 2 == 1) res = (res * base) % K;
// Square the base and reduce modulo K for the next iteration.
// Avoid unnecessary square if exp is 1 (already handled by loop condition `exp > 0`).
if (exp > 1)
base = (base * base) % K;
// Halve the exponent (integer division)
exp /= 2;
}
return res;
}
// Map to store results for the first half permutations.
// Key: The multiset of digits used in the first half permutation (represented by CountsArray).
// Value: A map where {key=remainder mod K, value=count of permutations yielding this remainder}.
std::map<CountsArray, std::map<int, long long>> map1;
// Recursive function to generate permutations for the first half (length N1 = N/2).
// k: current length of the permutation being built.
// current_used_counts: counts of digits used so far in this permutation.
// current_rem: remainder modulo K of the number formed by the permutation built so far.
// target_len: the desired length for the first half (N1).
void generate_first_half(int k, CountsArray current_used_counts, int current_rem, int target_len) {
// Base case: A permutation of length N1 has been formed.
if (k == target_len) {
// Store the result: increment the count for the state (multiset used, remainder).
map1[current_used_counts][current_rem]++;
return;
}
// Recursive step: Try appending each digit 'd' from 1 to 9.
for (int d = 1; d <= 9; ++d) {
// Check if digit 'd' is available (i.e., we haven't used up all instances of digit 'd').
if (current_used_counts[d] < initial_counts[d]) {
// Create the state for the next recursive call.
CountsArray next_used_counts = current_used_counts;
next_used_counts[d]++; // Increment count for digit 'd'.
// Calculate the new remainder: (current_rem * 10 + d) % K.
// Use long long for the intermediate multiplication to prevent overflow before modulo K.
int next_rem = (int)(((long long)current_rem * 10LL + d) % K);
// Make the recursive call to build the permutation further.
generate_first_half(k + 1, next_used_counts, next_rem, target_len);
}
}
}
// Cache to store results for second half permutations. This avoids recomputing for the same multiset.
// Key: The multiset of digits used for the second half permutation.
// Value: A map {key=remainder mod K, value=count of permutations yielding this remainder}.
std::map<CountsArray, std::map<int, long long>> map2_cache;
// Helper recursive function to generate permutations for the second half.
// This function is similar to generate_first_half, but operates on a specific 'available_counts' multiset.
// k: current length of permutation being built.
// current_used_counts: counts of digits used so far within the 'available_counts' multiset.
// current_rem: remainder modulo K of the number formed so far.
// target_len: desired length (N2 = N - N1).
// available_counts: the specific multiset of digits this half must use.
// results: map passed by reference to store the final {remainder -> count} results for this multiset.
void generate_second_half_recursive(int k, CountsArray current_used_counts, int current_rem, int target_len, const CountsArray& available_counts, std::map<int, long long>& results) {
// Base case: A permutation of length N2 has been formed.
if (k == target_len) {
// Store the result for this remainder.
results[current_rem]++;
return;
}
// Recursive step: Try appending each digit 'd' available in 'available_counts'.
for (int d = 1; d <= 9; ++d) {
// Check if digit 'd' is available within the 'available_counts' multiset.
if (current_used_counts[d] < available_counts[d]) {
// Prepare state for the next recursive call.
CountsArray next_used_counts = current_used_counts;
next_used_counts[d]++;
// Calculate new remainder.
int next_rem = (int)(((long long)current_rem * 10LL + d) % K);
// Recurse.
generate_second_half_recursive(k + 1, next_used_counts, next_rem, target_len, available_counts, results);
}
}
}
// Function to compute (and cache) or retrieve results for second half permutations for a specific multiset.
// counts_needed: The multiset of digits required for the second half.
// Returns a const reference to the map {remainder -> count} for the given multiset.
const std::map<int, long long>& get_second_half_results(const CountsArray& counts_needed) {
// Check if the results for this multiset are already in the cache.
auto cache_it = map2_cache.find(counts_needed);
if (cache_it == map2_cache.end()) {
// Not in cache: Compute the results.
std::map<int, long long> results;
CountsArray empty_counts = {0}; // Initial state for the recursive generation is empty counts used.
int target_len = 0; // Calculate the target length N2 for this half.
for(int i=1; i<=9; ++i) target_len += counts_needed[i];
// If N2 > 0, call the recursive generator.
if (target_len > 0) {
generate_second_half_recursive(0, empty_counts, 0, target_len, counts_needed, results);
} else {
// If N2 == 0, the second half is empty. The only 'permutation' forms the number 0.
// The remainder is 0, and there's 1 way to form it (the empty permutation).
results[0] = 1;
}
// Insert the computed results into the cache and get an iterator to the inserted element.
auto inserted_it = map2_cache.insert({counts_needed, results});
// Return a reference to the map value (the computed results).
return inserted_it.first->second;
} else {
// Found in cache: Return reference to the cached map.
return cache_it->second;
}
}
int main() {
// Use faster I/O.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read inputs N and K.
std::cin >> N >> K;
// Initialize counts array explicitly to zeros.
for (int i = 0; i <= 9; ++i) initial_counts[i] = 0;
// Read the counts for digits 1 through 9.
for (int i = 1; i <= 9; ++i) {
std::cin >> initial_counts[i];
}
// Handle the special case K=1. Any integer is divisible by 1.
// The answer is the total number of distinct permutations of the given digits.
if (K == 1) {
// Calculate N! / (c1! * c2! * ... * c9!).
std::vector<long long> fact(N + 1);
fact[0] = 1;
// Precompute factorials up to N. N<=14 fits within long long.
for(int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i;
long long total_perms = fact[N];
for(int i = 1; i <= 9; ++i) {
// Divide by factorial of counts for each digit type to account for duplicates.
if (initial_counts[i] > 1) {
// Check division by zero factorial - not possible here as fact[0]=1, fact[1]=1.
// This check is only relevant if N could be very large causing overflow, or counts could be 0.
if (fact[initial_counts[i]] == 0) { /* Error case, should not happen for N<=14 */ }
else total_perms /= fact[initial_counts[i]];
}
}
std::cout << total_perms << std::endl;
return 0;
}
// Determine lengths of the two halves for meet-in-the-middle.
int N1 = N / 2; // Length of the first half.
int N2 = N - N1; // Length of the second half.
// Generate permutations for the first half.
CountsArray empty_counts = {0}; // Start generation with empty set of used digits.
if (N1 > 0) { // Only generate if the first half has positive length.
generate_first_half(0, empty_counts, 0, N1);
} else {
// If N1 == 0 (occurs if N=0 or N=1), the first half is empty.
// The only 'permutation' is empty, forming value 0, remainder 0. There is 1 way.
map1[empty_counts][0] = 1;
}
// Initialize total count of valid permutations.
long long total_count = 0;
// Precompute 10^N2 mod K. This factor is needed to combine first and second half values.
long long p10_N2 = power(10, N2);
// Iterate through all results generated for the first half.
// Each entry represents a multiset `counts1` used and a map `rem_map1` of {remainder -> count}.
for (auto const& [counts1, rem_map1] : map1) {
// For the current `counts1`, determine the required multiset `counts2_needed` for the second half.
CountsArray counts2_needed = {0};
bool possible = true; // Flag to check if `counts2_needed` is valid.
int counts2_size = 0; // Keep track of the size of `counts2_needed`.
for (int i = 1; i <= 9; ++i) {
counts2_needed[i] = initial_counts[i] - counts1[i];
// If any count becomes negative, this `counts1` is invalid (shouldn't happen with correct generation).
if (counts2_needed[i] < 0) {
possible = false;
break;
}
counts2_size += counts2_needed[i];
}
// If the complement multiset `counts2_needed` is invalid or does not have the correct size N2, skip.
if (!possible || counts2_size != N2) continue;
// Get the results for the required second half multiset `counts2_needed`.
// This will compute results if not already cached.
const auto& rem_map2 = get_second_half_results(counts2_needed);
// Now combine the results from the first half (`rem_map1`) and second half (`rem_map2`).
// Iterate through each remainder `rem1` obtained for the first half multiset `counts1`.
for (auto const& [rem1, count1] : rem_map1) {
long long rem1_val = rem1; // The remainder value from the first half.
// Calculate the target remainder `target_rem2` needed for the second half.
// We need M = M_first * 10^N2 + M_last == 0 (mod K).
// So, M_last == -M_first * 10^N2 (mod K).
// Remainder calculation needs care with potential negative results from modulo.
long long term1 = (-rem1_val * p10_N2);
// Ensure the final target remainder is positive, in the range [0, K-1].
long long target_rem2 = (term1 % K + K) % K;
// Check if this `target_rem2` exists in the results map for the second half (`rem_map2`).
auto it = rem_map2.find(target_rem2);
if (it != rem_map2.end()) {
// If found, `count2` is the number of ways the second half can yield `target_rem2`.
long long count2 = it->second;
// The total number of ways for this combination is count1 * count2. Add to total count.
total_count += count1 * count2;
}
}
}
// Print the final total count.
std::cout << total_count << std::endl;
return 0;
}