题解：P10066 [CCO 2023] Binaria

· · 题解

Solution

一道考察差分约束与组合计数的题。

设原二进制字符串为 b_1,b_2,\dots,b_N \in \{0,1\}，题目给出的 SMS 序列为 A_1,A_2,\dots,A_{N-K+1}，其中 A_i = \sum_{j=i}^{i+K-1} b_j。

考虑相邻两个窗口的和：

A_{i+1} - A_i = b_{i+K} - b_i \quad (1 \le i \le N-K)

因为 b_i 只取 0 或 1，所以差值只能是 -1,0,1。由此我们得到：

对于相等关系，用并查集维护，同时在合并时优先让已知值的集合作为代表。这样处理完所有 i 后，所有位置被划分成若干个连通块，同一块内的位必须取相同值，部分块的值已经确定为 0 或 1。

注意到，滑动窗口的递推式 b_{i+K} = A_{i+1} - A_i + b_i 表明：一旦前 K 位的值确定，整个序列就会被唯一确定。与此同时，上述差分约束在 i+K 与 i 之间连边，不断前推必然使每个连通块都至少包含一个属于前 K 位的元素。因此，我们只需关心前 K 位中的连通块取值情况。

设前 K 位中，值未确定的连通块个数为 cnt，值已确定为 1 的连通块个数为 c_1。由于前 K 位的和必须等于 A_1，我们需要从 cnt 个未知块中选出恰好 A_1 - c_1 个赋值为 1，其余赋值为 0。这样的方案数即为组合数 \binom{cnt}{A_1-c_1}。

模数 10^6+3 是质数，预处理阶乘后用费马小定理求逆元即可计算组合数。由于未知块个数不超过 K，阶乘只需预处理到 K。

总时间复杂度 O(N\alpha(N))，可以轻松通过 N \le 10^6 的数据范围。

::::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e6 + 3;
int n,k,a[MOD],b[MOD],jc[MOD],fa[MOD],cnt;
int _find(int x){
    if(x == fa[x])
        return x;
    return fa[x] = _find(fa[x]);
}
int qpow(int x,int y){
    int res = 1;
    while(y){
        if(y & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> k;

    jc[0] = 1;
    for(int i = 1;i <= k;i++)
        jc[i] = jc[i - 1] * i % MOD;

    for(int i = 1;i <= n;i++)
        fa[i] = i,b[i] = -1;
    cin >> a[1];
    for(int i = 2;i <= n - k + 1;i++){
        cin >> a[i];
        cnt = a[i] - a[i - 1];
        if(cnt == 1)
            b[i + k - 1] = 1,b[i - 1] = 0;
        else if(cnt == -1)
            b[i + k - 1] = 0,b[i - 1] = 1;
        else{
            int x = _find(i - 1);
            int y = _find(i + k - 1);
            if(b[x] != -1)
                fa[y] = x;
            else
                fa[x] = y;
        }
    }
    cnt = 0;
    for(int i = 1;i <= k;i++)
        if(b[_find(i)] == -1)
            cnt++;
    for(int i = 1;i <= k;i++)
        if(b[_find(i)] == 1)
            a[1]--;
    cout << jc[cnt] * qpow(jc[a[1]],MOD - 2) % MOD * qpow(jc[cnt - a[1]],MOD - 2) % MOD << '\n';
    return 0;
}

::::