結果
| 問題 |
No.1631 Sorting Integers (Multiple of K) Easy
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,379 bytes |
| コンパイル時間 | 1,234 ms |
| コンパイル使用メモリ | 102,276 KB |
| 実行使用メモリ | 138,332 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:53 |
| 合計ジャッジ時間 | 7,312 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 11 TLE * 5 -- * 12 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <utility> // For std::pair
#include <functional> // For std::hash
using namespace std;
// Custom hash function for std::pair<long long, int>
// This is necessary to use std::pair as a key in std::unordered_map.
// Using a good hash combination technique helps reduce collisions and improve performance.
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1, T2>& p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
// Combine the hashes. A common method is inspired by boost::hash_combine.
// This approach helps in distributing hash values better and potentially reducing collisions.
size_t seed = 0;
// Combine h1 into seed
seed ^= h1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// Combine h2 into seed
seed ^= h2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
// Encodes the counts vector (c_1, ..., c_9) into a single long long integer.
// The problem constraints state N <= 14. This means each digit count c_i will also be <= 14.
// Since 14 < 16 = 2^4, each count can be represented using 4 bits.
// There are 9 digits (1 through 9), so the total number of bits needed is 9 counts * 4 bits/count = 36 bits.
// This fits comfortably within a 64-bit long long integer type.
long long encode_counts(const vector<int>& counts) {
long long code = 0;
for (int i = 0; i < 9; ++i) {
// Shift the current code left by 4 bits to make space for the next count.
// Then, bitwise OR the count into the lowest 4 bits.
code = (code << 4) | counts[i];
}
return code;
}
// DP state storage: An array of unordered_maps.
// dp[k] will store the dynamic programming states for prefixes of length k.
// The key of the map is a std::pair<long long, int> representing (encoded_counts, remainder).
// The value associated with the key is a long long storing the number of ways (distinct permutations) to reach that state.
// The array size is 15 to accommodate N up to 14 (using indices 0 through 14).
unordered_map<pair<long long, int>, long long, pair_hash> dp[15];
// Stores the initial counts c_1 through c_9 provided in the input.
vector<int> initial_counts(9);
int N; // Total number of digits.
int K; // The divisor K.
int main() {
// Enable fast I/O operations for potentially large inputs/outputs.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read N (total number of digits) and K (the divisor) from standard input.
cin >> N >> K;
// Read the initial counts for digits 1 through 9.
for (int i = 0; i < 9; ++i) {
cin >> initial_counts[i];
}
// Initialize the DP table with the base case.
// A prefix of length 0 uses zero counts for all digits.
// The value of an empty prefix is considered 0. The remainder modulo K is 0.
// There is exactly one way to form an empty prefix (the empty sequence).
vector<int> zero_counts(9, 0);
long long initial_code = encode_counts(zero_counts);
dp[0][{initial_code, 0}] = 1;
// Perform the dynamic programming state transitions level by level.
// Iterate through prefix lengths k from 0 up to N-1.
for (int k = 0; k < N; ++k) {
// Optimization: If dp[k] is empty, it means no valid prefixes of length k could be formed.
// This implies no prefixes of length k+1 or greater can be formed either. We can stop the process early.
if (dp[k].empty()) {
break;
}
// Iterate through all states reachable at the current level k.
// Each entry in the map dp[k] is a pair: {state_key, count_value}.
// 'state' is the key: pair<long long, int> = (encoded_counts, remainder).
// 'count' is the value: long long = number of ways to reach this state.
for (auto const& [state, count] : dp[k]) {
// If the count for a state is 0, it means this state is practically unreachable (or already processed leading to zero paths). Skip it.
if (count == 0) continue;
long long current_code = state.first;
int current_rem = state.second;
// Decode the 'current_code' back into a vector of counts.
// This is necessary to check the availability of each digit 'd' for appending to the prefix.
vector<int> current_counts(9);
long long temp_code = current_code;
// Decode the counts from the encoded long long. The counts are stored from most significant bits (digit 9) to least significant (digit 1).
// We decode from right to left (index 8 down to 0) to extract counts correctly.
for (int i = 8; i >= 0; --i) {
current_counts[i] = temp_code & 0xF; // Extract the count for digit i+1 using bitwise AND with mask 1111 (0xF).
temp_code >>= 4; // Shift right by 4 bits to process the next count stored in higher bits.
}
// Try appending each possible digit 'd' (from 1 to 9).
for (int d = 1; d <= 9; ++d) {
// Check if digit 'd' is available in the multiset.
// This is true if the count of 'd' used so far (current_counts[d-1])
// is less than the total count of 'd' available initially (initial_counts[d-1]).
if (current_counts[d - 1] < initial_counts[d - 1]) {
// If digit 'd' is available:
// Compute the counts vector for the new prefix (length k+1).
vector<int> next_counts = current_counts;
next_counts[d - 1]++; // Increment the count for the digit 'd' that was just used.
long long next_code = encode_counts(next_counts); // Encode this new counts vector into a long long key.
// Compute the remainder of the new prefix value modulo K.
// The new prefix value is conceptually (old_prefix_value * 10 + d).
// By modular arithmetic properties: new_remainder = (old_remainder * 10 + d) % K.
// Perform the calculation using 'long long' for the intermediate multiplication `(long long)current_rem * 10`
// to prevent potential integer overflow, although with K <= 1000 it might be safe for `int`. Using `long long` is safer.
int next_rem = (int)(((long long)current_rem * 10 + d) % K);
// Update the DP table for level k+1.
// Add the number of ways ('count') to reach the current state
// to the total ways count for the 'next_state'. This accumulates counts from different paths leading to the same state.
dp[k + 1][{next_code, next_rem}] += count;
}
}
}
// Optional memory optimization: If memory usage becomes a concern, one could potentially clear dp[k]
// after it's fully processed, as it won't be needed for subsequent levels k+2 onwards.
// Example: dp[k].clear(); dp[k].rehash(0);
// However, this might incur performance overhead due to map reallocations. Given the 512MB limit, it's likely unnecessary for N=14.
}
// After the loops complete, the final answer is stored in dp[N].
// We are interested in the count for the state that represents using exactly the initial multiset of digits
// (encoded by 'final_code') and results in a remainder of 0 modulo K.
long long final_code = encode_counts(initial_counts);
// Check if the target state {final_code, 0} exists in the map dp[N].
// Using .count() is a safe way to check existence without potentially inserting a new element if the key is not found (unlike operator[]).
if (dp[N].count({final_code, 0})) {
// If the state exists, its associated value is the answer. Print it.
cout << dp[N][{final_code, 0}] << endl;
} else {
// If the state {final_code, 0} was never reached, it means no permutation
// of the given digits forms a number divisible by K. The count is 0.
cout << 0 << endl;
}
return 0;
}