2021 CCPC 威海M 题解

2023/11/15 算法竞赛 数学 CCPC 2021 威海 生成函数

这题在vp的时候做出来了，但是今天在做2023CCPC秦皇岛的热身赛的时候发现这道题又想了很久才做出来，于是决定还是把思路写一遍

链接

题意

给一个长为 的01串，其中1有 个，最长连续的1的个数为 ，求不同的串的个数

解

最长连续的1的个数为 的不太好做，可以转化为最长连续的1的个数不超过 ，这样不用去考虑那个 是谁

由容斥原理可以知道最长连续1的个数为 的串数 = 最长连续的1的个数不超过 的串数 - 最长连续的1的个数不超过 的串数

这种不超过多少的问题可以转化为一个多元方程，例如这个题可以转化为
并且
的解的个数，其中 为一个连续1的段中1的个数， 为连续1的段的段数

但这样搞需要遍历 ，复杂度不够，无法通过此题，于是考虑优化

可以想到一个类似的但较弱的问题（想不起来具体是什么，只记得可以将一些元素绑定起来然后用隔板法解决），然后给了某种启发。

原序列中有 个位置，有 个1，去掉这 个1后有 个0。原问题可以化成在这些0中间插入1的串，每个串长不超过 。

个0有 个空位，于是可以写出母函数：

中 的 次方项系数 为

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
#define dmp(x) cerr<<"DEBUG"<<__LINE__<<":"<<#x<<" "<<x<<endl
const ll INF=0x3f3f3f3f3f3f3f3fLL;
typedef pair<int,int> pii;
const int mod=998244353;
const int N=1e5+100;
int fac[N],rev[N];
ll qpow(ll a,ll n,ll m)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
            ans=(__int128_t)ans*a%m;
        a=(__int128_t)a*a%m;
        n>>=1;
    }
    return ans;
}
void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    rev[n]=qpow(fac[n],mod-2,mod);//n must be less than mod
    for(int i=n;i>=1;i--)
        rev[i-1]=rev[i]*i%mod;
    assert(rev[0]==1);
}
int C(int n,int m)
{
    if(m>n)
        return 0;
    return fac[n]*rev[m]%mod*rev[n-m]%mod;
}
inline int cal(int n,int m,int k){
    int ans=0;
    for(int i=0;i*(k+1)<=m;i++){
        ans=(ans+(i%2==0?1:-1)*C(n-m+1,i)%mod*C(n-i*(k+1),n-m)%mod)%mod;
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    init(1e5+10);
    if(!(m<=n&&k<=m)){
        cout<<0<<'\n';
        return 0;
    }
    if(k==0){
        if(m==0)
            cout<<1<<'\n';
        else
            cout<<0<<'\n';
        return 0;
    }
    cout<<((cal(n,m,k)-cal(n,m,k-1))%mod+mod)%mod<<'\n';
    return 0;
}
img_show