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

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

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

其中，$\sum c_i\le 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$个字母。

• 第一种决策：放偶数位

  $f[i][j]=f[i][j]+(s[i]-j\le Rands[i-1]\ge j)\times f[i-1][j]\times C_{R-(s[i-1]-j)}^{c[i]}$ 其中$s[i]={\sum }_{k=1}^i{c}_k$

• 第二种决策：放奇数位

  $f[i][j]=f[i][j]+(j-c[i]\le Landj\ge 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]$

---

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

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

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

---

代码如下：

#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;
}