結果
| 問題 |
No.603 hel__world (2)
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:02:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 13,041 bytes |
| コンパイル時間 | 1,347 ms |
| コンパイル使用メモリ | 103,084 KB |
| 実行使用メモリ | 91,364 KB |
| 最終ジャッジ日時 | 2025-05-14 13:04:17 |
| 合計ジャッジ時間 | 7,042 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 11 TLE * 1 -- * 18 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <queue>
#include <algorithm> // Required for std::min/max
#include <string> // Required for std::reverse
// Using __int128_t for large integer arithmetic if available.
// This type is typically available in GCC/Clang compilers.
#ifdef __GNUC__
typedef __int128_t u128;
#else
// Fallback or error if __int128_t is not available
#warning "__int128_t not supported, using long long. Large values might overflow."
typedef long long u128;
// Note: This fallback is likely insufficient for the constraints.
#endif
// Function to print __int128_t (useful for debugging)
#ifdef __GNUC__
std::ostream& operator<<(std::ostream& os, u128 val) {
if (val < 0) {
os << "-";
val = -val;
}
if (val == 0) {
return os << "0";
}
std::string s = "";
while (val > 0) {
s += (char)('0' + (val % 10));
val /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
#endif
// Array to store maximum counts for each character 'a' through 'z'.
long long S_counts[26];
// The target subsequence string T.
std::string T;
// The modulus N = 10^6 + 3.
const int MOD = 1e6 + 3;
// Modular Arithmetic structure (Modint)
struct Modint {
long long val;
Modint(long long v = 0) {
// Ensure value is non-negative before taking modulo
if (v < 0) v = v % MOD + MOD;
val = v % MOD;
}
// Normalize value to be within [0, MOD-1]
void normalize() {
if (val < 0) val = val % MOD + MOD;
val %= MOD;
}
// Overloaded operators for modular arithmetic
Modint& operator+=(const Modint& other) {
val += other.val;
if (val >= MOD) val -= MOD;
return *this;
}
Modint& operator-=(const Modint& other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
Modint& operator*=(const Modint& other) {
val = (val * other.val) % MOD;
return *this;
}
// Modular exponentiation (for division via modular inverse)
static Modint power(Modint base, long long exp) {
Modint res = 1;
base.normalize();
while (exp > 0) {
if (exp % 2 == 1) res *= base;
base *= base;
exp /= 2;
}
return res;
}
// Modular inverse using Fermat's Little Theorem (since MOD is prime)
Modint inv() const {
return power(*this, MOD - 2);
}
Modint& operator/=(const Modint& other) {
*this *= other.inv();
return *this;
}
// Friend operators for convenience
friend Modint operator+(Modint a, const Modint& b) { return a += b; }
friend Modint operator-(Modint a, const Modint& b) { return a -= b; }
friend Modint operator*(Modint a, const Modint& b) { return a *= b; }
friend Modint operator/(Modint a, const Modint& b) { return a /= b; }
};
// Precomputed factorials and inverse factorials for combinations calculation
const int MAX_N_MOD = 1e6 + 3;
Modint fact[MAX_N_MOD];
Modint invFact[MAX_N_MOD];
// Precomputes factorials and inverse factorials modulo MOD up to MAX_N_MOD - 1.
void precompute_combinations() {
fact[0] = 1;
for (int i = 1; i < MAX_N_MOD; ++i) {
fact[i] = fact[i - 1] * Modint(i);
}
// Compute inverse factorial using modular inverse of the largest factorial
invFact[MAX_N_MOD - 1] = fact[MAX_N_MOD - 1].inv();
for (int i = MAX_N_MOD - 2; i >= 0; --i) {
invFact[i] = invFact[i+1] * Modint(i+1);
}
}
// Computes combinations C(n, r) modulo MOD using precomputed values.
// Uses Lucas' Theorem property implicitly: C(n, r) % MOD = C(n % MOD, r % MOD) % MOD.
Modint nCr_mod(long long n, long long r) {
// Basic validity checks
if (r < 0 || r > n) return Modint(0);
// Apply property based on Lucas' Theorem
long long n_mod = n % MOD;
// Since |T| <= 10^6 and MOD = 10^6+3, r corresponds to l_j which is <= |T| < MOD.
// So r % MOD = r.
// If r > n % MOD, then C(n % MOD, r) = 0.
if (r > n_mod) return Modint(0);
// Calculate C(n_mod, r) using factorials
return fact[n_mod] * invFact[r] * invFact[n_mod - r];
}
// Structure to represent ratios for priority queue comparisons.
// Uses __int128_t to handle potentially large numerators and denominators.
struct Ratio {
u128 num, den;
// Constructor initializes ratio, ensures positive denominator.
Ratio(u128 n = 0, u128 d = 1) : num(n), den(d) {
// Denominator should always be positive based on problem logic (k >= l >= 1 implies k+1-l >= 1).
// Add safety check and normalization just in case.
if (den == 0) {
den = 1; // Avoid division by zero issues.
} else if (den < 0) {
num = -num; den = -den;
}
}
// Comparison operator for priority queue ordering (max heap).
// Compares A/B < C/D as A*D < C*B to avoid floating point.
bool operator<(const Ratio& other) const {
return num * other.den < other.num * den;
}
// Other comparison operators (useful for checks)
bool operator>(const Ratio& other) const {
return other < *this;
}
bool operator>=(const Ratio& other) const {
return !(*this < other);
}
bool operator==(const Ratio& other) const {
return num * other.den == other.num * den;
}
};
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read maximum counts for each character
for (int i = 0; i < 26; ++i) {
std::cin >> S_counts[i];
}
// Read target subsequence string T
std::cin >> T;
// Handle empty T case (problem states |T| >= 1, but good practice)
if (T.empty()) {
std::cout << 1 << std::endl;
return 0;
}
// Compute T' (T after collapsing consecutive chars) and corresponding block lengths l_j.
std::string T_prime = "";
std::vector<long long> l_values;
if (!T.empty()) {
T_prime += T[0];
l_values.push_back(1);
for (size_t i = 1; i < T.length(); ++i) {
if (T[i] == T[i - 1]) {
l_values.back()++;
} else {
T_prime += T[i];
l_values.push_back(1);
}
}
}
int p = T_prime.length(); // Number of blocks in T'
// If T resulted in empty T', handle appropriately (e.g., T itself was empty)
if (p == 0) {
std::cout << 1 << std::endl; // Assuming convention for empty string T
return 0;
}
// Initialize k_j values (block lengths in S) to minimum required l_j.
std::vector<long long> k_values = l_values;
// Calculate total required count L_alpha for each character based on T.
std::map<char, long long> L_alpha;
for(int j=0; j<p; ++j) {
L_alpha[T_prime[j]] += l_values[j];
}
// Calculate remaining budget R_alpha for each character and total remaining budget R_total.
std::vector<long long> R_alpha(26); // Use long long for budgets
u128 R_total_128 = 0; // Use 128-bit integer for total budget
bool possible = true;
for (char alpha = 'a'; alpha <= 'z'; ++alpha) {
long long required = L_alpha.count(alpha) ? L_alpha[alpha] : 0;
// Check if available count S_counts is sufficient
if (S_counts[alpha - 'a'] < required) {
possible = false;
break;
}
// Calculate remaining budget
R_alpha[alpha - 'a'] = S_counts[alpha - 'a'] - required;
// Add to total budget only if positive
if (R_alpha[alpha - 'a'] > 0)
R_total_128 += (u128)R_alpha[alpha - 'a'];
}
// If constraints cannot be met, output 0.
if (!possible) {
std::cout << 0 << std::endl;
return 0;
}
// Precompute factorials and inverse factorials for nCr calculations.
precompute_combinations();
// Priority queue to manage blocks based on their current ratio (potential gain).
// Stores pairs of (Ratio, block_index). Max heap based on Ratio comparison.
std::priority_queue<std::pair<Ratio, int>> pq;
for (int j = 0; j < p; ++j) {
long long L = l_values[j];
// Initial ratio is (L+1)/1 because k_j starts at L.
Ratio r = { (u128)L + 1, 1 };
pq.push({r, j});
}
// Greedy distribution of remaining budget using batch updates
while (R_total_128 > 0 && !pq.empty()) {
std::pair<Ratio, int> top = pq.top();
pq.pop();
int j1 = top.second; // Index of the block with highest ratio
char c = T_prime[j1]; // Character of this block
int alpha_idx = c - 'a'; // Index for budget array
// Skip if budget for this character is already zero
if (R_alpha[alpha_idx] == 0) continue;
Ratio ratio1 = top.first; // The ratio of the current top block
Ratio ratio2 = {1, 1}; // Default minimum ratio is 1/1 (effectively lowest possible gain)
// Peek at the next element's ratio to determine batch size
if (!pq.empty()) {
ratio2 = pq.top().first;
}
long long K = k_values[j1]; // Current length k_j1
long long L = l_values[j1]; // Required length l_j1 (constant)
u128 current_K_128 = K; // Use 128-bit for calculations
// Binary search to find the maximum number of increments `max_x` such that
// the ratio of block j1 after `max_x` increments is still >= ratio2.
u128 low = 0, high = R_alpha[alpha_idx], max_x = 0;
// Check function: returns true if ratio at K+x is >= ratio2
auto check_mid = [&](u128 current_k_plus_x) {
// Ensure k value is valid
if (current_k_plus_x < L) return false;
u128 num = current_k_plus_x + 1;
u128 den = current_k_plus_x + 1 - L;
// Check denominator validity (should always be >= 1)
if (den <= 0) return false;
Ratio current_ratio = { num, den };
return current_ratio >= ratio2;
};
// Check if K+0 is valid (it should be, as it's ratio1 >= ratio2)
if (check_mid(current_K_128)) {
max_x = 0; // Base case: 0 increments is valid
low = 1; // Start searching for positive increments
high = R_alpha[alpha_idx]; // Search up to the budget limit
while(low <= high) {
// Midpoint calculation avoiding overflow for large low/high
u128 mid;
// Check for potential overflow before addition
if (high > low) {
mid = low + (high - low) / 2;
} else {
mid = low; // or high, they are equal
}
if (mid == 0 && low > 0) break; // Prevent infinite loop if low becomes 1, mid=0. Should check mid range.
// Use check_mid with K + mid
if (check_mid(current_K_128 + mid)) {
max_x = mid; // mid increments is possible, try larger
low = mid + 1; // Need to check for overflow on mid+1 for u128?
if (low == 0) break; // Overflow occurred if low wraps around
} else {
high = mid - 1; // mid increments is too much, try smaller
}
}
} // else: initial check failed, indicates potential issue. max_x remains 0.
// Number of increments to perform: max_x found + 1 (greedy step)
u128 num_increments_128 = max_x + 1;
// Clamp the number of increments by available budgets
num_increments_128 = std::min(num_increments_128, (u128)R_alpha[alpha_idx]);
num_increments_128 = std::min(num_increments_128, R_total_128);
// If budget is positive but calculated increments is 0, force at least 1 increment
if (num_increments_128 == 0 && R_alpha[alpha_idx] > 0 && R_total_128 > 0) {
num_increments_128 = 1;
}
// If still 0 increments (e.g., budget exhausted), continue
if (num_increments_128 == 0) continue;
// Update k_value, budgets
long long num_increments = (long long)num_increments_128; // Cast back to long long
k_values[j1] += num_increments;
R_alpha[alpha_idx] -= num_increments;
R_total_128 -= num_increments_128;
// Push the updated block back into the priority queue with its new ratio
Ratio new_ratio = { (u128)k_values[j1] + 1, (u128)k_values[j1] + 1 - L };
pq.push({new_ratio, j1});
}
// Calculate the final product of combinations modulo MOD
Modint final_product = 1;
for (int j = 0; j < p; ++j) {
final_product *= nCr_mod(k_values[j], l_values[j]);
}
// Output the result
std::cout << final_product.val << std::endl;
return 0;
}