結果
| 問題 |
No.2313 Product of Subsequence (hard)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:25 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,031 bytes |
| コンパイル時間 | 1,655 ms |
| コンパイル使用メモリ | 103,800 KB |
| 実行使用メモリ | 16,072 KB |
| 最終ジャッジ日時 | 2025-05-14 13:15:41 |
| 合計ジャッジ時間 | 11,383 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 1 -- * 16 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <vector>
#include <cmath> // Not strictly needed but can be useful
#include <algorithm> // For std::min
// Define the modulus
const long long MOD = 998244353;
// Modular exponentiation: computes (base^exp) % MOD
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
// Structure to hold a prime factor and its required exponent in K
struct PrimeFactor {
long long p; // prime factor
int e; // required exponent
};
// Function to prime factorize K
// Returns a vector of PrimeFactor structs
std::vector<PrimeFactor> prime_factorize(long long k) {
std::vector<PrimeFactor> factors;
long long temp_k = k; // Use a temporary variable to preserve k if needed
// Iterate through potential prime factors up to sqrt(temp_k)
for (long long i = 2; i * i <= temp_k; ++i) {
if (k % i == 0) { // If i is a factor of k
int count = 0;
// Divide k by i repeatedly and count the occurrences
while (k % i == 0) {
k /= i;
count++;
}
// Store the prime factor and its exponent
factors.push_back({i, count});
}
}
// If k is still greater than 1 after the loop, the remaining k is a prime factor itself
if (k > 1) {
factors.push_back({k, 1});
}
return factors;
}
int main() {
// Use fast I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of elements in sequence A
long long K; // The divisor K
std::cin >> N >> K;
std::vector<long long> A(N); // Sequence A
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
// Handle the trivial case K=1
// Any non-empty subsequence product is a multiple of 1.
// The total number of non-empty subsequences is 2^N - 1.
if (K == 1) {
long long total_subsequences = power(2, N);
long long ans = (total_subsequences - 1 + MOD) % MOD; // Calculate (2^N - 1) mod MOD
std::cout << ans << std::endl;
return 0;
}
// Factorize K into its prime factors and their exponents
std::vector<PrimeFactor> k_factors = prime_factorize(K);
int m = k_factors.size(); // Number of distinct prime factors of K
// Calculate the size of each dimension in the DP state space
// The k-th dimension corresponds to the prime factor p_k, and its size is e_k + 1
std::vector<int> E_plus_1(m);
for (int i = 0; i < m; ++i) {
E_plus_1[i] = k_factors[i].e + 1;
}
// Calculate the total state space size E = product(e_k + 1)
// And precompute bases for mapping multi-dimensional state to a single index
long long E = 1; // Total number of states
std::vector<long long> Bases(m + 1); // Bases B_k for mixed radix representation
Bases[0] = 1;
for (int i = 0; i < m; ++i) {
// Check for potential overflow before multiplication, though unlikely given constraints
if (__builtin_mul_overflow(E, E_plus_1[i], &E)) {
// This case should not happen for K <= 10^9, as max E is around 512.
// Handle error or indicate issue if needed.
}
// Calculate Bases[i+1] = B_{i+1} = B_i * (e_i + 1)
Bases[i+1] = Bases[i] * E_plus_1[i];
}
// The final value E represents the total size of the DP state space.
// DP state table initialization
// dp[idx] stores the number of subsequences processed so far that map to state index idx.
std::vector<long long> dp(E, 0);
dp[0] = 1; // Base case: The empty subsequence corresponds to state index 0 (all exponents 0), count is 1.
// Process each element A[i] of the sequence
for (int i = 0; i < N; ++i) {
// Compute the capped exponent vector V' for the current element A[i]
// V'[k] = min(exponent of p_k in A[i], required exponent e_k)
std::vector<int> V_prime(m);
long long current_A = A[i]; // Use a copy of A[i] to modify during factorization
for (int k = 0; k < m; ++k) {
int count = 0;
// Efficiently compute the exponent of p_k in A[i], capped at e_k
while (count < k_factors[k].e && current_A > 0 && current_A % k_factors[k].p == 0) {
current_A /= k_factors[k].p;
count++;
}
V_prime[k] = count; // Store the computed capped exponent
}
// Prepare the DP table for the next state (after processing A[i])
std::vector<long long> next_dp = dp; // Initialize with current dp state counts. This represents subsequences *not* including A[i].
// Iterate through all current states idx from 0 to E-1
for (int idx = 0; idx < E; ++idx) {
if (dp[idx] == 0) continue; // Skip states with zero count for efficiency
// Calculate the index 'next_idx' of the state resulting from including A[i]
long long current_state_val = idx; // Use a temporary variable for clarity
int next_idx = 0; // Initialize index for the next state
// Calculate components s'_k of the next state S' and combine them into next_idx
for(int k=0; k<m; ++k) {
// Extract k-th component s_k (current exponent for p_k) from current index idx
// using integer division and modulo with the precomputed bases.
int sk = (current_state_val / Bases[k]) % E_plus_1[k];
// Compute k-th component of the next state: s'_k = min(s_k + v'_k, e_k)
int sk_prime = std::min(sk + V_prime[k], k_factors[k].e);
// Accumulate s'_k into the flat index next_idx using base B_k
next_idx += (long long)sk_prime * Bases[k];
}
// Add the count dp[idx] (number of subsequences reaching state idx)
// to the count of the computed next state index 'next_idx'.
// This represents subsequences that *do* include A[i].
next_dp[next_idx] = (next_dp[next_idx] + dp[idx]) % MOD;
}
// Update the DP table for the next iteration using move semantics for potential efficiency gain.
dp = std::move(next_dp);
}
// Calculate the index corresponding to the target state (e1, e2, ..., em)
// This state represents products that are multiples of K.
int target_idx = 0;
for(int k=0; k<m; ++k) {
target_idx += (long long)k_factors[k].e * Bases[k];
}
// The final answer is the count stored in the target state dp[target_idx].
// Since K > 1, the target state is not the initial state (index 0),
// so dp[target_idx] correctly counts only non-empty subsequences satisfying the condition.
std::cout << dp[target_idx] << std::endl;
return 0;
}