CCPC Weihai 2021m eight hundred and ten thousand nine hundred and seventy-five

M. 810975

The question

the $n$ game , win victory $m$ game , One of the longest winning streak is $k$, Ask how many situations .

Answer key

consider $an{s}_k$ by ： the $n$ game , win victory $m$ game , One of the longest winning streak Greater than or equal to $k$, Ask how many situations .
Because there is $n-m$ Negative fields , So consider the surrounding of each negative field as empty Then insert the victory .
enumeration $i$ The continuous length is greater than or equal to $k$ Wins , Enumerate the locations of these consecutive wins empty , The number is ${(}_i^{n-m+1})$, Then the next arbitrary allocation can , The number of options is ${(}_{n-m}^{n-ik})$, so
$$an{s}_k=\sum _{i=1}^{m-i\ast k>=0}(-1{)}^{i+1}{(}_i^{n-m+1}){(}_{n-m}^{n-ik})$$

The final output $an{s}_{k+1}-an{s}_k$ that will do

Special , If you consider generating functions , Enumerate each empty The number of winning fields inside can be made by polynomial fast power , The maximum win is less than or equal to $k$ The number of schemes can be determined by
$$an{s}_k=(1+x^2+..+x^k{)}^{n-m+1}=(\frac{1-x^k+1}{1-x}{)}^{n-m+1}$$
The number of times is m Expressed by the term coefficient of , Then the answer is $an{s}_k-an{s}_{k-1}$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
ll poww(ll a,ll b)
{
    
    ll t=1;
    while(b)
    {
    
        if(b&1)t=t*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return t;

}
ll P1[300005],P2[300005];
void init()
{
    
    P1[0]=P2[0]=1;
    for(int i=1;i<=300000;i++)P1[i]=P1[i-1]*i%mod;
    P2[300000]=poww(P1[300000],mod-2);
    for(int i=299999;i>=1;i--)P2[i]=P2[i+1]*(i+1)%mod;
}
ll C(ll n,ll m)
{
    
    return P1[n]*P2[m]%mod*P2[n-m]%mod;
}
int main()
{
    
    init();
    long long n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    ll ans=0;
    if(k==0)
    {
    
        printf("%d\n",m==0);
        return 0;
    }
    for(ll i=1;i*k<=m;i++)
    {
    
        if(i&1)ans=(ans+C(n-m+1,i)*C(n-i*k,n-m)%mod)%mod;
        else ans=(ans-C(n-m+1,i)*C(n-i*k,n-m)%mod)%mod;
// printf("ans=%lld\n",ans);
    }
    k++;
    for(ll i=1;i*k<=m;i++)
    {
    
        if(i&1)ans=(ans-C(n-m+1,i)*C(n-i*k,n-m)%mod)%mod;
        else ans=(ans+C(n-m+1,i)*C(n-i*k,n-m)%mod)%mod;
    }
    printf("%lld",(ans%mod+mod)%mod);

    return 0;
}

I don't know why I'm so stupid $B$ The title of the game will be stuck ？