CF2086D Even String 题目详解
题目概述
本题需要将字符串中的奇数位和偶数位分离，形成两条独立序列 A 和 B。同一字母必定出现在同一条序列中。
数学公式推导
设序列 A 上分配了 a、b、c 三种字母，对应数量分别为 ca、cb、cc，记 sum = ca + cb + cc，则序列 A 的排列方案数为：
\[ans_A = \frac{sum!}{c_a! \cdot c_b! \cdot c_c!} \]
同理，序列 B 上分配了 d、e、f 三种字母，对应数量为 cd、ce、cf，记 sum' = cd + ce + cf，则序列 B 的排列方案数为：
\[ans_B = \frac{sum'!}{c_d! \cdot c_e! \cdot c_f!} \]
因此，对于该种字母分配方式，总方案数为 ansA × ansB：
\[ans = \frac{sum!\cdot sum'!}{c_a! \cdot c_b! \cdot c_c! \cdot c_d! \cdot c_e! \cdot c_f!} \]
可以发现，无论如何分配字母种类，只要分配合法，该分配方式的方案数量恒为 ans。由于 ci 为定值，可直接计算出 ans。由于涉及取模除法，需要求逆元。模数 998244353 为质数，可利用费马小定理求逆元。
分配方案数计算
接下来需要计算序列 A、B 的字母种类分配方案数，有两种实现方法：双向深度优先搜索和动态规划。
方法一：双向深度优先搜索
字母种类共有 26 种，测试数据量高达 104，直接枚举需要约 1012 次操作，会超时。若将 26 分为两部分，每部分 13 种，则计算量约为 108，可以接受。因此采用双向搜索策略。
为提高效率，使用哈希表记录每种 A、B 序列的字母种类分配方案数。由于涉及二维映射，可将二维状态压缩为一维整数存储。最终答案为 cnt × ans，其中 cnt 为分配方案数。
注意事项：计算 ans 时，阶乘不能预处理，否则会超出时间限制（实测约 100ms）。需要采用在线计算方式。
参考实现：
#include <iostream>
#include <cstring>
#include <algorithm>
#include
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int MAXN = 500010;
const int LETTERS = 26;
const int HALF_LETTERS = 13;
int half1, half2;
int letterCnt[35];
int totalWays;
int fac[MAXN], invFac[MAXN];
unordered_map<long long, int> memo;
int modPow(int a, int k) {
int res = 1;
while (k) {
if (k & 1) res = (ll)res * a % MOD;
k >>= 1;
a = (ll)a * a % MOD;
}
return res;
}
int computeFact(int x) {
int res = 1;
for (int i = 1; i <= x; i++) {
res = (ll)res * i % MOD;
}
return res;
}
int computeInvFact(int x) {
int res = 1;
for (int i = 1; i <= x; i++) {
res = (ll)res * i % MOD;
}
return modPow(res, MOD - 2);
}
void searchFirst(int idx, int sum1, int sum2) {
if (idx > HALF_LETTERS) {
long long key = (long long)sum1 * MAXN + sum2;
memo[key]++;
return;
}
if (letterCnt[idx] == 0) {
searchFirst(idx + 1, sum1, sum2);
} else {
if (sum1 + letterCnt[idx] <= half1) {
searchFirst(idx + 1, sum1 + letterCnt[idx], sum2);
}
if (sum2 + letterCnt[idx] <= half2) {
searchFirst(idx + 1, sum1, sum2 + letterCnt[idx]);
}
}
}
void searchSecond(int idx, int sum1, int sum2) {
if (idx > LETTERS) {
long long key = (long long)(half1 - sum1) * MAXN + (half2 - sum2);
totalWays += memo[key];
return;
}
if (letterCnt[idx] == 0) {
searchSecond(idx + 1, sum1, sum2);
} else {
if (sum1 + letterCnt[idx] <= half1) {
searchSecond(idx + 1, sum1 + letterCnt[idx], sum2);
}
if (sum2 + letterCnt[idx] <= half2) {
searchSecond(idx + 1, sum1, sum2 + letterCnt[idx]);
}
}
}
int main() {
int T;
cin >> T;
while (T--) {
memo.clear();
totalWays = 0;
int total = 0;
for (int i = 1; i <= LETTERS; i++) {
scanf("%d", &letterCnt[i]);
total += letterCnt[i];
}
sort(letterCnt + 1, letterCnt + 1 + LETTERS);
reverse(letterCnt + 1, letterCnt + 1 + LETTERS);
half1 = total / 2;
half2 = (total + 1) / 2;
searchFirst(1, 0, 0);
searchSecond(HALF_LETTERS + 1, 0, 0);
int result = 1;
for (int i = 1; i <= LETTERS; i++) {
result = (ll)result * computeInvFact(letterCnt[i]) % MOD;
}
ll answer = (ll)totalWays * computeFact(half1) % MOD;
answer = answer * computeFact(half2) % MOD;
answer = answer * result % MOD;
cout << answer << '\n';
}
return 0;
} 方法二：动态规划（01背包）
将每种字母视为物品，字母数量视为体积。问题转化为：在 26 种字母中选择若干种，使得选中的字母总数量恰好等于奇数位字符数量 sum 的方案数。时间复杂度为 O(nm)，其中 m ≤ 5×105，总计算量约 107 次，完全可以通过，且效率高于双向搜索。
参考实现：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int MAXN = 500010;
const int LETTERS = 26;
int half1, half2;
int letterCnt[35];
int totalWays;
int dp[MAXN];
int modPow(int a, int k) {
int res = 1;
while (k) {
if (k & 1) res = (ll)res * a % MOD;
k >>= 1;
a = (ll)a * a % MOD;
}
return res;
}
int computeFact(int x) {
int res = 1;
for (int i = 1; i <= x; i++) {
res = (ll)res * i % MOD;
}
return res;
}
int computeInvFact(int x) {
int res = 1;
for (int i = 1; i <= x; i++) {
res = (ll)res * i % MOD;
}
return modPow(res, MOD - 2);
}
int main() {
int T;
cin >> T;
while (T--) {
totalWays = 0;
int total = 0;
for (int i = 1; i <= LETTERS; i++) {
scanf("%d", &letterCnt[i]);
total += letterCnt[i];
}
sort(letterCnt + 1, letterCnt + 1 + LETTERS);
reverse(letterCnt + 1, letterCnt + 1 + LETTERS);
half1 = total / 2;
half2 = (total + 1) / 2;
for (int i = 0; i <= half1; i++) {
dp[i] = 0;
}
dp[0] = 1;
for (int i = 1; i <= LETTERS; i++) {
if (letterCnt[i] == 0) break;
for (int j = half1; j >= letterCnt[i]; j--) {
dp[j] += dp[j - letterCnt[i]];
}
}
totalWays = dp[half1];
int result = 1;
for (int i = 1; i <= LETTERS; i++) {
result = (ll)result * computeInvFact(letterCnt[i]) % MOD;
}
ll answer = (ll)totalWays * computeFact(half1) % MOD;
answer = answer * computeFact(half2) % MOD;
answer = answer * result % MOD;
cout << answer << '\n';
}
return 0;
}总结
本题核心在于将奇偶位分离后，分别计算两条序列的排列方案数和字母种类分配方案数。排列方案数可通过组合数学公式直接计算，而分配方案数可采用双向搜索或动态规划求解。动态规划方法代码更简洁，效率也更高。
