2024.09.19短时训练赛总结

$ T1 $

感觉没有蓝，只有中绿左右。
赛时写了正解，漏了个 $ + $ 号，寄了，然后逆元处理了 $ inv $，但是不知道为什么写的是快速幂，于是就 T 了。
考虑枚举两端改变，中间随便的区间 $ [i,j] $，然后乱搞即可。
$ \color{black}{zzzcr} $ 有一个 $ O(n) $ 的做法是考虑双指针，然后对于有交的区间减去中间重叠的部分。
实际上赛时这题一眼是想到双指针的，但是没有仔细想，因为看到 $ 1\le n \le 5000 $，觉得正解大概是 $ O(n^2) $ 的，就没有继续调。
不过 $ O(n) $ 的算法框架，大体是想到了的，差不多到减去中间重叠的部分。
唉，太菜了。

//AsahinaMafuyu
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5010, MOD = 998244353;

int n, k;
char a[N];
int res, f[N][N];
int C[N][N];
//设f[i][j]表示区间[i, j]改变的方案数（i, j改变，其他随便）
int fac[N], inv[N];

int qp(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) (res *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }

    return res;
}

int C_(int n, int m)
{
    if (n < 0 || m < 0) return 0;
    return C[n][m];
}

signed main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    C[0][0] = 1;
	for (int i = 1; i <= n; i ++ )
    {
		C[i][0] = 1;
		for (int j = 1; j <= i; j ++ )
			(C[i][j] = C[i - 1][j - 1] + C[i - 1][j]) %= MOD;
	}
    fac[0] = 1, a[0] = '0';
    for (int i = 1; i <= n; i ++ ) (fac[i] = fac[i - 1] * i) %= MOD;
    inv[n] = qp(fac[n], MOD - 2);
    for (int i = n - 1; ~i; i -- ) inv[i] = inv[i + 1] * (i + 1) % MOD;
    int sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int j, s = 0, s0 = 0, s1 = 0;
        if (a[i] == '1') s ++ ;
        sum += s;
        if (a[i] == '1') s1 ++ , s0 -- ;
        else s0 ++ , s1 -- ;
        for (j = i + 1; j <= n; j ++ )
        {
            s += a[j] - '0';
            if (s > k) break;
            s0 += '1' - a[j], s1 += a[j] - '0';
            if (a[j] == '1') s0 -- ;
            else s1 -- ;
            (f[i][j] += C_(s0 + s1, s1)) %= MOD;
            if (a[j] == '1') s0 ++ ;
            else s1 ++ ;
        }
        if (s < k && j <= n) 
            for (int j = i + 1; j <= n; j ++ ) 
                f[i][j] = 0;
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            (res += f[i][j]) %= MOD;
    if (sum < k) res = 0;

    cout << (res + 1) % MOD << '\n';

    return 0;
}

$ T2, T3 $ 再说吧。