当前位置：首页 > news >正文

【codeforces 2086d】背包+组合数学

news 来源：原创 2025/5/19 6:33:03

【codeforces 2086d】背包+组合数学

Problem - D - Codeforces
题意：
给出字符串中每个字符的出现次数 $c_i(1 \leq i \leq 26)$ 。现构造一个字符串，要求任意相同字母之间的距离必须是偶数。求满足要求的字符串的数量。

其中， $\sum c_i \leq 5 \times 10^5$

例如， $c[27] = {2,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}$ ，可以构造出的字符串有 $4$ 个： $abak$ ， $akab$ ， $baka$ ， $kaba$ 。

思路：
我们发现对于一个字母来说，我们必须将其全部放在奇数位或者全部放在偶数位，才能保证任意相同字母之间的距离必须是偶数。

也就是说，对于字母 $x$ 来说，我们有两种决策方式：将其全部放入奇数位；将其全部放入偶数位。

同时，我们发现位数是有限的。考虑(背包)动态规划。

首先计算出奇数有 $L$ 位，偶数有 $R$ 位。令 $f [i] [j]$ 表示考虑第 $i$ 个字符，决策完后，奇数位放了 $j$ 个字母。

第一种决策：放偶数位

$\leq R \ \ and\ \ s[i - 1] \geq j) \times f[i - 1][j] \times C_{R - (s[i - 1] - j)}^{c[i]}$ 其中 $\sum_{k = 1}^{i}c_k$
第二种决策：放奇数位

$\leq L \ \ and \ \ j \geq c[i]) \times f[i - 1][j - c[i]] \times C_{L - (j - c[i])}^{c[i]}$

$C$ 表示组合数，预处理组合数可用 $C_n^m = \frac{n!}{m!(n - m)!} = fact[n] \times infact[m] \times infact[n - m]$

我认为动态规划问题通常考虑在问题规模缩小和扩大时，变量是什么。

例如此题，在构造字符串这个问题规模不断缩小和扩大时，奇数位的数量在变化。同时，我们考虑的字母也是不同的。我们不妨将此都加入状态中思考怎么转移。此外，我们还可以基于熟悉的背包模型，思考此题的状态。在方案数的计算上，我们更容易体会到 $d p$ 数组记录一类方案，直接查表的过程。

在观察一道题是否是动态规划时，或转移方程是什么时，我通常思考有哪些决策。例如此题，我们经过推理，得到决策后，动态规划的转移方程也呼之欲出。在 $a c w in g$ 的动态规划讲解中，如何决策也等同于如何划分集合。

代码如下：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"const int n = 26, N = 30, M = 5e5 + 10, mod = 998244353;
LL c[N], s[N];
LL fact[M], infact[M];
LL f[N][M];LL qmi(LL a, LL b) {LL res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}LL inv(LL a) {return qmi(a, mod - 2);
}LL comb(LL a, LL b) {return fact[a] % mod * infact[b] % mod * infact[a - b] % mod;
}void init(int n) {fact[0] = 1;for (int i = 1; i <= n; i ++) fact[i] = fact[i - 1] * i % mod;infact[n] = inv(fact[n]);for (int i = n - 1; i >= 0; i --) infact[i] = infact[i + 1] * (i + 1) % mod;
}void solve() {for (int i = 1; i <= n; i ++) cin >> c[i];memset(s, 0, sizeof s);for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + c[i];LL L = 0, R = 0;if (s[n] & 1) {L = s[n] / 2 + 1, R = s[n] - L;} else {L = s[n] / 2, R = s[n] / 2;}for (int i = 1; i <= n; i ++) {for (int j = 0; j <= s[i]; j ++) {f[i][j] = 0;}}f[0][0] = 1;for (int i = 1; i <= n; i ++) {if (!c[i]) {for (int j = 0; j <= min(s[i], L); j ++) {f[i][j] = f[i - 1][j];}continue;}for (int j = 0; j <= min(s[i], L); j ++) {if (s[i] - j <= R && s[i - 1] >= j) {f[i][j] += f[i - 1][j] * comb(R - s[i - 1] + j, c[i]) % mod;f[i][j] %= mod;}if (j >= c[i] && L - j + c[i] >= 0) {f[i][j] += f[i - 1][j - c[i]] * comb(L - j + c[i], c[i]) % mod;f[i][j] %= mod;}}}cout << f[n][L] << endl;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init(M - 1);int t; cin >> t;while (t --) solve();return 0;
}

【codeforces 2086d】背包+组合数学

相关文章：