CF1622D. Shuffle 题解 组合数学/枚举

题目链接：​​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​​