题解：P10066 [CCO 2023] Binaria

_dyqdyq_ · 2026-08-08 14:25:13 · 题解

模拟赛题，简单题。

看到大部分题解都比我的写法稍微复杂一点，补一发题解。

可以发现每当 SMS 序列第 i 位比第 i + 1 位少 1 时，则原序列第 i 位是 0，第 i + k 位是 1。反之亦然，当第 i 位比第 i + 1 位多 1 时，则原序列第 i 位是 1，第 i + k 位是 0。

但当SMS序列第 i 位等于第 i + 1 位时，则原序列中第 i 位和第 i + k 位一定相等。

我们只需根据这三条规则将原序列尽可能填满，我们就会发现一个神秘的事情，原序列每 k 位所没填的数量一定相等，所需要填的 1 的数量也相等，证明很简单，这里就不说了。其实只要多手玩几组样例就行

根据这个结论，我们只需算原序列前 k 个中有多少种方案即可，答案就是 \binom{num0}{num1}，num1就是前 k 个中还需要的 1 的数量，num0 就是前 k 中还没填的位置数。

时间复杂度 O(n)

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5,mod = 1e6 + 3;
int n,k,fac[maxn],inv[maxn],a[maxn],b[maxn],num1[maxn],num0[maxn];
inline int qpow(int a,int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}
inline void init()
{
    fac[0] = 1;
    for(int i = 1;i < maxn;i++)
    {
        fac[i] = (fac[i - 1] * i % mod);
    }
    return ;
}
inline int C(int n,int m)
{
    if(n > m)
        return -1;
    else
        return (fac[m] * qpow(fac[n],mod - 2) % mod * qpow(fac[m - n],mod - 2)) % mod;
}
bool vis[maxn];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    init();
    cin >> n >> k;
    memset(b,-1,sizeof(b));
    int m = n - k + 1;
    for(int i = 1;i <= m;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i < m;i++)
    {
        if(a[i] < a[i + 1])
        {
            b[i] = 0;
            b[i + k] = 1;
        }
        else if(a[i] > a[i + 1])
        {
            b[i] = 1;
            b[i + k] = 0;
        }
    }
    for(int i = 1;i < m;i++)
    {
        if(b[i] != -1 && a[i] == a[i + 1])
        {
            b[i + k] = b[i];
        }
    }
    for(int i = m;i > 1;i--)
    {
        if(b[i] != -1 && b[i - k] == -1)
        {
            b[i - k] = b[i];
        }
    }
    int cnt1 = 0,cnt0 = 0;
    for(int i = 1;i <= k;i++)
    {
        if(b[i] == 0)
            cnt0++;
        else if(b[i] == 1)
            cnt1++;
    }
    cout << C(a[1] - cnt1,k - cnt0 - cnt1) << "\n";
    /*
    for(int i = 1;i <= n;i++) 
    {
        cout << b[i] << " ";
    }
    cout << "\n";
    */
    return 0;
}
/*
7 4
3 2 2 2
*/