M. 810975(容斥原理)

M. 810975

n场比赛赢了m场，其中最长有k场连胜，容斥

AC代码：

#include 
using namespace std;
using LL = long long;
const int mod = 998244353;
LL a[100010], inva[100010];
void in(int &x) {
    x = 0; char ee = getchar();
    while(ee > '9' || ee < '0') ee = getchar();
    while(ee <= '9' && ee >= '0') x = (x << 3) + (x << 1) + ee - '0' , ee = getchar();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    in(n);
    in(m);
    in(k);
    if (k == 0) {
        if (m == 0) {
            cout << "1\n";
        } else {
            cout << "0\n";
        }
        exit(0);
    }
    a[0] = a[1] = 1;
    inva[0] = inva[1] = 1;
    function qp = [&](LL a, LL b) {
        LL res = 1;
        for (; b; b >>= 1, a = a * a % mod) {
            if (b & 1) {
                res = res * a % mod;
            }
        }
        return res;
    };
    for (int i = 1; i <= 100001; i++) {
        a[i] = (a[i - 1] * i) % mod;
    }
    inva[100001] = qp(a[100001], mod - 2);
    for (int i = 100000; i >= 1; i--) {
        inva[i] = (inva[i + 1] * (i + 1)) % mod;
    }
    function C = [&](LL x, LL y) {
        if (x < y or x < 0 or y < 0) {
            return 0ll;
        }
        return ((a[x] * inva[x - y]) % mod) * inva[y] % mod;
    };
    functionint)> calc = [&](int z) {
        LL res = 0;
        for (int i = 1; i * z <= m; i++) {
            if (i & 1) {
                res = (res + C(n - m + 1, i) * C(n - i * z, n - m) % mod) % mod;
            } else {
                res = (res - C(n - m + 1, i) * C(n - i * z, n - m) % mod + mod) % mod;
            }
        }
        return res % mod;
    };
    cout << (calc(k) - calc(k + 1) + mod) % mod << '\n';
    return 0;
}