結果
| 問題 |
No.1956 猫の額
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:08 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,272 bytes |
| コンパイル時間 | 702 ms |
| コンパイル使用メモリ | 80,232 KB |
| 実行使用メモリ | 32,200 KB |
| 最終ジャッジ日時 | 2025-05-14 13:03:11 |
| 合計ジャッジ時間 | 23,266 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | MLE * 1 -- * 20 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
// Using C-style arrays allocated dynamically via `new` to potentially reduce memory overhead
// compared to std::vector<std::vector<int>>.
// Using `int` for counts modulo M, as M fits within a standard 32-bit signed integer.
// Helper function to compute the DP table for a given subset of items A.
// dp[k][s] will store the number of ways to choose exactly k items with sum s.
// N_items: number of items in the subset A
// max_k: maximum number of items to choose from this subset (e.g., N1 for the first subset)
// max_s: maximum possible sum from this subset (e.g., S1 for the first subset)
// M: modulus
void compute_dp(const std::vector<int>& A, int** dp, int N_items, int max_k, int max_s, int M) {
// Base case: Choosing 0 items results in sum 0 in exactly 1 way.
dp[0][0] = 1;
// Iterate through each item in the subset A
for (int item_idx = 0; item_idx < N_items; ++item_idx) {
int item = A[item_idx];
// Iterate downwards for k (number of items chosen) to ensure that each item
// is considered at most once for inclusion in a subset.
for (int k = max_k; k >= 1; --k) {
// Iterate downwards for s (sum)
for (int s = max_s; s >= item; --s) {
// Check if state (k-1, s-item) is reachable (count > 0)
// This state represents choosing k-1 items with sum s-item from elements before the current one.
if (dp[k - 1][s - item] > 0) {
// If reachable, we can form state (k, s) by adding the current item.
// Add the number of ways to reach state (k-1, s-item) to the count for state (k, s).
// Perform addition modulo M.
dp[k][s] = (dp[k][s] + dp[k - 1][s - item]) % M;
}
}
}
}
}
int main() {
// Optimize standard I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of integers
long long M_ll; // Modulus (up to 10^9, fits in long long)
int C; // Exact number of items to choose
std::cin >> N >> M_ll >> C;
int M = (int)M_ll; // Cast M to int; safe since M <= 10^9 < 2^31
std::vector<int> A(N); // Input array of integers
long long total_sum_A_ll = 0; // Use long long for sum calculation potentially exceeding 2^31
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
total_sum_A_ll += A[i];
}
// Total sum S = sum(A_i) <= 10^5, fits within int.
int S = (int)total_sum_A_ll;
// Split the N items into 3 roughly equal parts for meet-in-the-middle strategy.
// This aims to reduce peak memory usage compared to a 2-way split.
int N1 = N / 3;
int N2 = N / 3;
int N3 = N - N1 - N2; // The remaining items
// Create sub-vectors for each part
std::vector<int> A1(A.begin(), A.begin() + N1);
std::vector<int> A2(A.begin() + N1, A.begin() + N1 + N2);
std::vector<int> A3(A.begin() + N1 + N2, A.end());
// Calculate maximum possible sums for each part
long long S1_ll = 0; for(int x : A1) S1_ll += x; int S1 = (int)S1_ll;
long long S2_ll = 0; for(int x : A2) S2_ll += x; int S2 = (int)S2_ll;
long long S3_ll = 0; for(int x : A3) S3_ll += x; int S3 = (int)S3_ll;
// Allocate DP tables using C-style 2D arrays dynamically.
// Initialize all counts to 0 using '()'.
int** dp1 = new int*[N1 + 1];
for(int i=0; i<=N1; ++i) dp1[i] = new int[S1 + 1]();
compute_dp(A1, dp1, A1.size(), N1, S1, M);
int** dp2 = new int*[N2 + 1];
for(int i=0; i<=N2; ++i) dp2[i] = new int[S2 + 1]();
compute_dp(A2, dp2, A2.size(), N2, S2, M);
int** dp3 = new int*[N3 + 1];
for(int i=0; i<=N3; ++i) dp3[i] = new int[S3 + 1]();
compute_dp(A3, dp3, A3.size(), N3, S3, M);
// Final answer array. Use long long for intermediate sum calculations during combination
// to prevent overflow before taking modulo M, though counts themselves are mod M.
std::vector<long long> ans(S + 1, 0);
// Combination step: Combine results from the 3 DP tables.
// This uses nested loops iterating through reachable states (k, s) in each table.
// This step has high time complexity and is likely the bottleneck (potential TLE).
// An efficient solution would use FFT/NTT here, but that's complex to implement
// correctly under tight memory constraints.
for (int k1 = 0; k1 <= N1; ++k1) { // Iterate through number of items chosen from Part 1
for (int s1 = 0; s1 <= S1; ++s1) { // Iterate through possible sums from Part 1
if (dp1[k1][s1] == 0) continue; // Skip if this state is unreachable
long long ways1 = dp1[k1][s1]; // Number of ways for this state
for (int k2 = 0; k2 <= N2; ++k2) { // Iterate through number of items chosen from Part 2
if (k1 + k2 > C) continue; // Optimization: If k1+k2 already exceeds C, cannot reach target C.
for (int s2 = 0; s2 <= S2; ++s2) { // Iterate through possible sums from Part 2
if (dp2[k2][s2] == 0) continue; // Skip unreachable states
if (s1 + s2 > S) continue; // Optimization: If sum s1+s2 already exceeds total S, cannot reach valid final sum.
long long ways2 = dp2[k2][s2];
// Precompute (ways1 * ways2) % M. Use long long for multiplication before modulo.
long long ways12 = (ways1 * ways2) % M;
// Determine the required number of items from Part 3
int k3_target = C - (k1 + k2);
// Check if this required number k3_target is valid (within bounds 0 to N3)
if (k3_target >= 0 && k3_target <= N3) {
// Iterate through possible sums from Part 3 for the target k3
for (int s3 = 0; s3 <= S3; ++s3) {
if (dp3[k3_target][s3] == 0) continue; // Skip unreachable states
int final_s = s1 + s2 + s3; // Calculate final sum
if (final_s > S) continue; // Optimization: Check if final sum exceeds total S
long long ways3 = dp3[k3_target][s3];
// Calculate the contribution of this combination: (ways12 * ways3) % M
long long term = (ways12 * ways3) % M;
// Add this contribution to the total count for final_s
ans[final_s] = (ans[final_s] + term) % M;
}
}
}
}
}
}
// Deallocate the dynamically allocated DP tables to free memory
for(int i=0; i<=N1; ++i) delete[] dp1[i]; delete[] dp1;
for(int i=0; i<=N2; ++i) delete[] dp2[i]; delete[] dp2;
for(int i=0; i<=N3; ++i) delete[] dp3[i]; delete[] dp3;
// Output the final counts for each sum s from 1 to S
for (int s = 1; s <= S; ++s) {
std::cout << ans[s] << (s == S ? "" : " ");
}
std::cout << std::endl;
return 0;
}