2021 CCPC 威海 M 810975 容斥

题意:问有多少种长度为n的01串，其中1的总个数为m，最长的连续1的长度为k

解法:看到要精准计算k，考虑转化一下，计算最长的连续1的长度小于等于k的方案数-计算最长的连续1的长度小于k的方案数，那么就是我们想要的答案。
我们记最长的连续1的长度小于等于k的方案数为 $a n s_{k}$
$a n s_{k}$ 的计算方式可以考虑容斥，容斥长度大于k的有多少段。那么 $a n s_{k}$ =0段连续1的长度大于k - 1段连续1的长度大于k + 2段连续1的长度大于k .... i段连续1的长度大于k

对于i段连续1的长度大于k的方案计算方式，可以直接相当于这些段的1的数量为(k+1)。

由于此时剩余的位置为 $n - i * (k + 1)$ ,还有 $n - m$ 个负场，选取方式为 $C (n - i * (k + 1), n - m)$ ,所以总的选取方式为 $C (n, i) * C (n - i * (k + 1), n - m)$ 到这里差不多就结束了，贴上代码

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define set9 fixed<<setprecision(9)
#define set12 fixed<<setprecision(12)
#define set2 fixed<<setprecision(2)
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define db double
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=2e5+5;
const ll mod=998244353;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
ll fact[maxn];
ll inv[maxn];
inline ll Inverse(ll x) { return qpow(x,mod-2);}
inline ll C(ll n,ll m) { if(m>n||m<0) return 0; return fact[n]*inv[m]%mod*inv[n-m]%mod;}
void init(int n)
{
    ll f=1;
    fact[0]=inv[0]=1;
    for(int i=1;i<=n;i++)
    {
        f=f*i%mod;
        fact[i]=f;
    }
    inv[n]=qpow(f,mod-2);
    for(int i=n-1;i>=1;i--)
    {
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
    }
}

int solve(int n,int m,int k)
{
    int p=n-m+1;
    int flag=1,ans=0;
    rep(i,0,p)
    {
        if(n-i*(k+1)<n-m) continue;
        ll tmp=C(p,i)%mod,tmp2=C(n-i*(k+1),n-m)%mod;
        ans=(ans%mod+flag*(tmp*tmp2)%mod+mod)%mod;
        flag*=-1;
    }
    return ans;
}

signed main()
{
    int n=read(),m=read(),k=read();
    init(2*n);
    int ans=solve(n,m,k)-solve(n,m,k-1);
    printf("%lld\n",(ans+mod)%mod);
}