810975 (2021 CCPC Weihai M) - ペンギンの巣

Problem Summary#

You played $n$ games and won exactly $m$ of them. Your longest winning streak has length exactly $k$ . How many win/loss sequences match this? $(0 \le n, m, k \le 10^5)$

Approach#

At first glance this looks like a plain combinatorics problem, but it turns out to be tricky to count directly. Following Solemntee’s editorial, the trick is inclusion-exclusion. Let $ans_k$ be the number of sequences whose longest winning streak is at least $k$ . The answer we want is $ans_k - ans_{k+1}$ .

To compute $ans_k$ : first “reserve” the $m$ wins. Placing $i$ disjoint runs each of length at least $k$ can be encoded as choosing $i$ of the $n - m + 1$ candidate slots between/around the losses — that’s $\binom{n - m + 1}{i}$ . After committing $ik$ wins to those runs, the remaining $n - ik$ positions can hold the leftover wins and losses freely, contributing $\binom{n - ik}{n - m}$ . By inclusion-exclusion, $ans_k = \sum_{i \ge 1,\; ik \le m} (-1)^{i+1} \binom{n - m + 1}{i} \binom{n - ik}{n - m}.$ Handle the corner case $k = 0$ separately (the answer is $1$ iff $m = 0$ ), and you’re done.

Code#

1
#include<bits/stdc++.h>
2
using namespace std;
3
long long mod=998244353;
4
int MAX=100005;
5
vector<long long>fac,inv,finv;
6
void binom_init()
7
{
8
    fac.resize(MAX);
9
    finv.resize(MAX);
10
    inv.resize(MAX);
11
    fac[0] = fac[1] = 1;
12
    inv[1] = 1;
13
    finv[0] = finv[1] = 1;
14
    for (int i = 2; i < MAX; i++)
15
    {
16
        fac[i] = fac[i - 1] * i % mod;
17
        inv[i] = mod - mod / i * inv[mod % i] % mod;
18
        finv[i] = finv[i - 1] * inv[i] % mod;
19
    }
20
}
21
long long binom(long long n, long long r)
22
{
23
    if (n < r || n < 0 || r < 0) return 0;
24
    return fac[n] * finv[r] % mod * finv[n - r] % mod;
25
}
26
int main()
27
{
28
    binom_init();
29
    int n,m,k;
30
    scanf("%d%d%d",&n,&m,&k);
31
    if(k==0)
32
    {
33
        printf("%d\n",m==0);
34
        return 0;
35
    }
36
    long long ans1=0,ans2=0;
37
    for(long long i=1;i*k<=m;i++)
38
    {
39
        if(i&1)ans1=(ans1+binom(n-m+1,i)%mod*binom(n-i*k,n-m)%mod+mod)%mod;
40
        else ans1=(ans1-binom(n-m+1,i)%mod*binom(n-i*k,n-m)%mod+mod)%mod;
41
    }
42
    for(long long i=1;i*(k+1)<=m;i++)
43
    {
44
        if(i&1)ans2=(ans2+binom(n-m+1,i)%mod*binom(n-i*(k+1),n-m)%mod+mod)%mod;
45
        else ans2=(ans2-binom(n-m+1,i)%mod*binom(n-i*(k+1),n-m)%mod+mod)%mod;
46
    }
47
    printf("%lld\n",(ans1-ans2+mod)%mod);
48
    return 0;
49
}