CF2255B 题解

· · 题解

随便挑一个赛时会做的写个题解 /kel

朴素做法

似乎可以 O(n^2) 之类的做一个区间 dp，不是正解不说了（

正解

我们首先观察样例中的第一组。

初始时为：\mathtt{00110}。 可以通过选择 l=1,r=5 把它变为：\mathtt{01100}。

我们初步观察到一个性质：

一个形如 \mathtt{xx\dots xSxx\dots x} 的串（其中 \mathtt{S} 是一个子串，\mathtt{x} 是 \mathtt{0} 或 \mathtt{1}。暂时不考虑选择这个子串中的端点），我们可以把这个 \mathtt{S} 任意移动（或翻转）！

这个简单手玩可以发现。证明（以向左翻为例）大概是可以选择左右各一个端点，使得 \mathtt{S} 离右端点比左端点近，于是可以通过翻转把到两个端点的距离互换，于是可以到达左侧某一位置。如果想要把 \mathtt{S} 翻回原顺序只需要贴着 \mathtt{S} 左右两边选端点翻转。

这个性质有什么用呢？

事实上，这个操作可以等价于任意重分配 \mathtt{S} 两侧 \mathtt{x} 的数量（需要保证剩余数 \ge1）。

于是我们发现实际上每个连续段块长 -1 的和就是可以再分配的字符数量。

令 n_0 为可以再分配的 \mathtt{0} 数量，n_1 为可以再分配的 \mathtt{1} 数量，k_0 为 \mathtt{0} 的块数，k_1 为 \mathtt{1} 的块数。

使用隔板法求分割为非负块长数，答案即为：

C_{n_0+k_0-1}^{k_0-1}\times C_{n_1+k_1-1}^{k_1-1}

注意此时如果 C 的上下标值存在不合法情况应当返回 1，因为相当于无法重分配。

这个式子和官解的式子是等价的。

Code

这是赛时代码，调试代码有点多，实际上是快速幂写挂了……

// Author: albertting
// Time: 2026/08/09 23:47:28
#include <bits/stdc++.h>
#define __Made return
#define in 0
#define China__ ;
#define ll long long
#define ld long double
#define lll __int128
#define pb push_back
#define uset unordered_set
#define umap unordered_map
using namespace std;

const ll P = 998244353;

ll qpow(ll a, ll b) {
    if(b == 0) return 1;
    ll res = qpow(a, b >> 1);
    res = res * res % P;
    if(b & 1) res = res * a % P;
    return res;
}
ll fact[2000005], inv[2000005];

ll C(ll n, ll m) {
    if(n <= 0 || m <= 0) return 1;
    return fact[n] * inv[m] % P * inv[n - m] % P;
}

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll n0 = 0, n1 = 0, k0 = 0, k1 = 0;
    int l = 0;
    for(int r = 1; r < n; r++) {
        if(s[r] == s[l]) continue;
        if(s[l] == '0') n0 += r - l - 1, k0++;
        else n1 += r - l - 1, k1++;
        l = r;
    }
    if(s[l] == '0') n0 += n - l - 1, k0++;
    else n1 += n - l - 1, k1++;
    // clog << n0 << ' ' << k0 << ' ' << n1 << ' ' << k1 << '\n';
    // clog << C(n0 + k0 - 1, k0 - 1) << ' ' << C(n1 + k1 - 1, k1 - 1) << '\n';
    cout << C(n0 + k0 - 1, k0 - 1) * C(n1 + k1 - 1, k1 - 1) % P << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0), clog.tie(0);

    fact[0] = inv[0] = 1;
    for(ll i = 1; i <= 2000000; i++) {
        fact[i] = fact[i - 1] * i % P;
        inv[i] = qpow(fact[i], P - 2);
        // if(i <= 10) clog << i << ": " << fact[i] << ' ' << inv[i] << '\n';
    }
    int t; cin >> t;
    while(t--) solve();
    __Made in China__
}