题目链接:https://codeforces.com/problemset/problem/1622/D
题目大意:给定一个长度为 \(n\) 的 01字符串 \(s\),你可以对这个字符串进行最多一次操作,该次操作需要选择一个恰好包含 \(k\) 个 1 的子串,并将这个子串中的元素任意调整顺序。问:能够得到多少个不同的字符串(答案对 \(998244353\)
解题思路:
我们假设对一个子串进行位置的调整,其中最前面那个变化过的字符的位置是 \(i\),最后面那个变化过的字符的位置是 \(j\),则因为位置 \(i\) 和 \(j\) 变化过,统计一下 \(i\) 和 \(j\) 中间的元素个数(\(j - i - 1\) 个),然后再计算一下中间要放几个 1 和 0,如果区间 \([i+1, j-1]\) 范围内要放 \(c_1\) 个 1 和 \(c_0\) 个 0,则对答案的贡献为 \(C_{c_1 + c_0}^{c_1}\)(注意,可能会有些状态不合法,比如 \(k = 2\) 时子串是 "11" 就是不可行的,可以通过 \(c_1 \lt 0\) 或 \(c_0 \lt 0\)
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050;
const long long MOD = 998244353;
int n, k, sum[maxn], c[maxn][maxn];
char s[maxn];
long long ans = 1;
void init() {
c[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (j==0 || j==i) c[i][j] = 1;
else c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
}
}
}
int main() {
scanf("%d%d%s", &n, &k, s+1);
init();
for (int i = 1; i <= n; i++)
sum[i] = sum[i-1] + (s[i] == '1');
if (k > sum[n]) {
puts("1");
return 0;
}
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n && sum[j] - sum[i-1] <= k; j++) {
int c1 = sum[j] - sum[i-1], c0 = j - i + 1 - c1;
if (s[i] == '0') c1--;
else c0--;
if (s[j] == '0') c1--;
else c0--;
if (c0 >= 0 && c1 >= 0) {
ans = (ans + c[c0+c1][c1]) % MOD;
}
}
}
printf("%lld\n", ans);
return 0;
}
参考资料:https://codeforces.com/blog/entry/98453