結果
| 問題 |
No.295 hel__world
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,742 bytes |
| コンパイル時間 | 1,040 ms |
| コンパイル使用メモリ | 89,508 KB |
| 実行使用メモリ | 59,044 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:30 |
| 合計ジャッジ時間 | 8,425 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 21 WA * 7 TLE * 1 -- * 24 |
コンパイルメッセージ
main.cpp: In function ‘ull nCr_capped(uint128, int)’:
main.cpp:91:44: warning: left shift count >= width of type [-Wshift-count-overflow]
91 | uint128 max_uint128 = ((uint128)1 << 128) - 1; // Maximum value for __uint128_t
| ~~~~~~~~~~~^~~~~~
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <map> // Not strictly needed anymore but kept from development history
// Use unsigned long long for counts and DP values.
// This type can store values up to approximately 1.8e19.
using ull = unsigned long long;
// Use __uint128_t for intermediate calculations involving potentially large counts S_alpha
// and binomial coefficients, as these can exceed the range of unsigned long long.
// __uint128_t can store values up to approximately 3.4e38.
using uint128 = __uint128_t;
// Define the threshold value 2^62. If the result reaches or exceeds this, output "hel".
// Use unsigned long long literal suffix (ULL) for clarity.
const ull MAX_VAL = (1ULL << 62);
// Function for safe addition. If the sum reaches or exceeds MAX_VAL, it returns MAX_VAL.
// This prevents overflow and handles the threshold condition.
ull safe_add(ull a, ull b) {
// If either operand is already MAX_VAL or larger, the result should be MAX_VAL.
if (a >= MAX_VAL || b >= MAX_VAL) return MAX_VAL;
ull res;
// Check for potential overflow before addition: if a + b >= MAX_VAL?
// This check avoids overflow by rewriting as a >= MAX_VAL - b.
// Since MAX_VAL fits in ull, MAX_VAL - b is safe if b <= MAX_VAL.
if (b > MAX_VAL) { // Safety check, though b should already be capped
return MAX_VAL;
}
if (a >= MAX_VAL - b) {
res = MAX_VAL; // The sum would be >= MAX_VAL
} else {
res = a + b; // Addition is safe from overflow
}
// Final check just in case, although the logic above should cap correctly.
if (res >= MAX_VAL) return MAX_VAL;
return res;
}
// Function for safe multiplication. If the product reaches or exceeds MAX_VAL, it returns MAX_VAL.
ull safe_mul(ull a, ull b) {
// Base case: multiplication by zero is zero.
if (a == 0 || b == 0) return 0;
// If either operand is already capped, the result should also be capped.
// (Unless one is 1, but that check complicates things unnecessarily. If a or b >= MAX_VAL, result is large.)
if (a >= MAX_VAL || b >= MAX_VAL) {
// Consider edge case: 1 * MAX_VAL should be MAX_VAL. Handled if MAX_VAL >= MAX_VAL check is done first.
// Check if a=1 or b=1? No, the following 128-bit check handles it.
// Simplified: if one operand is >= MAX_VAL, result is >= MAX_VAL.
return MAX_VAL;
}
// Use 128-bit integers for intermediate multiplication to accurately check against MAX_VAL.
uint128 res128 = (uint128)a * b;
// Check if the 128-bit result meets or exceeds the threshold.
if (res128 >= MAX_VAL) {
return MAX_VAL; // Cap the result.
}
// If the result is within the threshold, cast back to ull.
return (ull)res128;
}
// Function to compute Binomial coefficient C(n, k), capping the result at MAX_VAL.
// Uses __uint128_t for intermediate calculations to handle large n.
ull nCr_capped(uint128 n, int k) {
// Check invalid k values.
if (k < 0) return 0;
uint128 k128 = k; // Use 128-bit k for comparisons with n.
if (k128 > n) return 0; // If k > n, C(n, k) is 0.
// Base cases. C(n, 0) = 1.
if (k == 0) return 1;
// Optimization: C(n, k) = C(n, n-k). Use the smaller k value.
if (k128 > n / 2) {
k128 = n - k128;
k = (int) k128; // Update integer k if it changed.
}
// Check if k became 0 after optimization. E.g. C(n,n) -> C(n,0).
if (k == 0) return 1;
// Iteratively compute C(n,k) = product_{i=1..k} (n-i+1)/i
// This avoids large intermediate factorials.
uint128 res = 1;
for (int i = 1; i <= k; ++i) {
uint128 term_num = n - i + 1; // Numerator term (n-i+1)
// Check for potential 128-bit overflow BEFORE multiplication.
uint128 max_uint128 = ((uint128)1 << 128) - 1; // Maximum value for __uint128_t
// Check if res * term_num would exceed the 128-bit limit.
if (term_num > 0 && res > max_uint128 / term_num) {
// Multiplication would overflow 128 bits. The true value is extremely large.
res = MAX_VAL; // Cap at MAX_VAL because it's certainly >= MAX_VAL.
break; // Stop calculation early.
}
res *= term_num; // Perform multiplication using 128-bit arithmetic.
// Perform division by i. In this calculation path, division must be exact.
res /= i;
// Check if the current result meets or exceeds MAX_VAL threshold.
if (res >= MAX_VAL) {
res = MAX_VAL; // Cap the result.
break; // Stop calculation early.
}
}
// Final check and return value cast back to ull.
if (res >= MAX_VAL) return MAX_VAL;
return (ull)res;
}
int main() {
// Use faster I/O operations.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read the maximum counts S_alpha for each character 'a' through 'z'.
std::vector<uint128> S_counts(26);
for (int i = 0; i < 26; ++i) {
unsigned long long count_ll; // Read as standard 64-bit first.
std::cin >> count_ll;
S_counts[i] = count_ll; // Store as 128-bit integer.
}
// Read the target subsequence string T.
std::string T;
std::cin >> T;
// Handle edge case of empty T string. Problem statement says |T| >= 1.
if (T.empty()) {
std::cout << 1 << std::endl; // Empty subsequence always appears once.
return 0;
}
// Compute the compressed version C(T) by removing consecutive duplicates.
std::string C_T = "";
C_T += T[0]; // Add the first character.
for (size_t i = 1; i < T.length(); ++i) {
if (T[i] != T[i-1]) { // If current char is different from previous...
C_T += T[i]; // ...add it to the compressed string.
}
}
int k = C_T.length(); // k is the length of C(T), number of blocks.
// Store the indices of blocks in C(T) corresponding to each character alpha.
// I_alpha[c] contains list of indices i such that C_T[i] == character c.
std::vector<std::vector<int>> I_alpha(26);
for (int i = 0; i < k; ++i) {
I_alpha[C_T[i] - 'a'].push_back(i);
}
// Determine the lengths l_i for each block S = c_1^{l_1} ... c_k^{l_k}.
// Use an even distribution heuristic: distribute S_alpha counts as evenly as possible
// among the blocks corresponding to character alpha.
std::vector<uint128> l(k);
bool possible = true; // Flag to track if S construction is possible.
for (int alpha = 0; alpha < 26; ++alpha) {
int N_alpha = I_alpha[alpha].size(); // Number of blocks for this character alpha.
if (N_alpha == 0) continue; // Skip if character alpha does not appear in C(T).
// Check if we have enough characters S_alpha to form N_alpha blocks (each length >= 1).
if (S_counts[alpha] < (uint128)N_alpha) {
possible = false; // Not enough characters.
break;
}
// Calculate base count and remainder for even distribution.
uint128 base_count = S_counts[alpha] / N_alpha;
uint128 remainder = S_counts[alpha] % N_alpha;
// Assign lengths l_i to blocks.
for (int idx = 0; idx < N_alpha; ++idx) {
int block_idx = I_alpha[alpha][idx];
l[block_idx] = base_count; // Assign base count.
if ((uint128)idx < remainder) { // First 'remainder' blocks get an extra count.
l[block_idx]++;
}
// Since S_counts[alpha] >= N_alpha > 0, each l_i is guaranteed to be at least 1.
}
}
// If it's impossible to form the required structure S, output 0.
if (!possible) {
std::cout << 0 << std::endl;
return 0;
}
// Initialize DP state vector dp. dp[p] stores the count of prefix T[0..p-1].
int m = T.length(); // Length of T.
std::vector<ull> dp(m + 1, 0);
dp[0] = 1; // Base case: empty prefix "" is subsequence once in any non-empty string S.
// Precompute positions in T for each character 'a'..'z'.
// pos_indices[c] stores 1-based indices p such that T[p-1] == c.
std::vector<std::vector<int>> pos_indices(26);
for(int i = 0; i < m; ++i) {
pos_indices[T[i]-'a'].push_back(i+1);
}
// Precompute Kp_map[p]: Stores the length of the run of character T[p-1] ending at index p-1 in T.
// Example: T = "aab", Kp_map[1]=1 ('a'), Kp_map[2]=2 ('a'), Kp_map[3]=1 ('b').
std::vector<int> Kp_map(m+1, 0);
for (int p_idx = 1; p_idx <= m; ++p_idx) {
if (p_idx > 1 && T[p_idx-1] == T[p_idx-2]) { // If current character matches previous...
Kp_map[p_idx] = Kp_map[p_idx-1] + 1; // ...increment run length.
} else {
Kp_map[p_idx] = 1; // ...otherwise start a new run of length 1.
}
}
// Main DP calculation loop: iterate through each block of S.
for (int i = 0; i < k; ++i) { // Process block i from 0 to k-1.
char c = C_T[i]; // Character of the current block.
uint128 current_l = l[i]; // Length of the current block (number of c's).
int char_idx = c - 'a'; // Index 0-25 for the character.
// Store a copy of the DP state *before* processing this block.
// The update formula relies on values from the previous state.
std::vector<ull> current_dp_copy = dp; // O(m) time complexity for copy.
// Get the list of positions p in T where T[p-1] == c.
const std::vector<int>& current_char_pos = pos_indices[char_idx];
// Update DP state for relevant positions p.
for (int p : current_char_pos) {
ull sum_val = 0; // Accumulator for the new dp[p] value.
// Get precomputed run length ending at index p-1 in T.
// This Kp is used in the summation limit for the update formula.
int current_Kp = Kp_map[p];
// Apply the DP update formula derived from matrix exponentiation:
// dp_new[p] = sum_{j=0..current_Kp} C(current_l, j) * dp_old[p-j]
for (int j = 0; j <= current_Kp; ++j) {
// Ensure index p-j is valid (non-negative).
if (p - j < 0) break;
// Compute binomial coefficient C(l, j), capped at MAX_VAL.
ull C_lj = nCr_capped(current_l, j);
// Get the dp value from the state before this block's update.
ull prev_dp_val = current_dp_copy[p - j];
// Compute the product C(l, j) * dp_old[p-j] using safe multiplication.
ull term_prod = safe_mul(C_lj, prev_dp_val);
// Add this term to the sum using safe addition.
sum_val = safe_add(sum_val, term_prod);
// Optimization: if sum already reached MAX_VAL, no need to add more terms.
if (sum_val >= MAX_VAL) break;
}
dp[p] = sum_val; // Update dp[p] with the computed sum.
}
// Early exit condition: if the count for the full subsequence T (dp[m]) reaches MAX_VAL,
// output "hel" and terminate.
if (dp[m] >= MAX_VAL) {
std::cout << "hel" << std::endl;
return 0;
}
}
// After processing all blocks, check the final count dp[m].
if (dp[m] >= MAX_VAL) {
std::cout << "hel" << std::endl; // Output "hel" if threshold reached.
} else {
std::cout << dp[m] << std::endl; // Otherwise, output the calculated count.
}
return 0;
}