CF1622D 题解

这么 sb 的题我居然没想出来，我太菜了 QAQ 。

---

link

给定长度为 $n$ 的 $01$ 序列 $a$，求进行一次一下操作后得到的不同的 $a$ 的方案数：

• 选定一段恰好含有 $k$ 个 $1$ 的区间，将这个区间内的元素随意排列。

$2 \le n \le 2 \times 5000$，$0 \le k \le n$，$a_i \in \{0,1\}$。

看到题后就有一个思路，枚举所有满足条件的区间，容斥计算答案。我们来康康可不可以。

首先只需要枚举极大的满足条件的区间即可，因为对于一对 $[L,R]$，如果 $[L-x,R+y]$ 也只有 $k$ 个 $1$，那 $[L,R]$ 的所有方案都会包含在 $[L-x,R+y]$ 中。

我们还可以发现一个性质：一个区间和后面任意区间的交集都包含在和这个区间相邻的区间的交里面。

用韦恩图表示差不多是这样：

所以不需要容斥，只要计算所有满足条件区间的和，减去两相邻区间的交的方案即可。看图好理解，模拟一下样例。

然后还有一个很妙的点：相邻的极大区间 $L$ 和 $R$ 都最多差 $1$。证明很简单，假设一个区间和与它相邻的差大于一，那么就是中间割了若干个零，这样的话这个区间就不是极大的了，可以把这串零再加进去。

既然最多差一，就可以算出所有相邻的极大区间的交集都有 $k - 1$ 个 $1$。所以只要枚举所有长度为 $k$ 和 $k - 1$ 的区间计算一下就好了，时间复杂度 $O(N^2)$。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
#define N 5010
#define P 998244353

int n, k, fac[N], inv[N], res = 1;
char a[N];

int Pow(int x, int k, int r = 1) {
    for (; k; k >>= 1, x = x * x % P)
        if (k & 1) r = r * x % P;
    return r;
}
void Mem() {
    fac[0] = 1;
    for (int i = 1; i < N; i ++) {
        fac[i] = fac[i - 1] * i % P;
    }
    inv[N - 1] = Pow(fac[N - 1], P - 2);
    for (int i = N - 2; i >= 0; i --) {
        inv[i] = inv[i + 1] * (i + 1) % P;
    }
}
int C(int n, int m) {
    if (n < m) return 0;
    return fac[n] * inv[m] % P * inv[n - m] % P;
}

signed main() {
    Mem();
    n = read(), k = read(), scanf("%s", a + 1);
    if (k == 0) return puts("1"), 0;
    a[0] = a[n + 1] = '1';
    for (int i = 1; i <= n; i ++) {
        if (a[i - 1] != '1') continue;
        for (int j = i, s = 0; j <= n; j ++) {
            s += (a[j] == '1');
            if (s == k - 1 && a[j + 1] == '1' && i != 1 && j != n) {
                (res += P + 1 - C(j - i + 1, k - 1)) %= P;
            } 
            if (s == k && a[j + 1] == '1') {
                (res += C(j - i + 1, k) - 1 + P) %= P;
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}