2021ccpc威海M题 810975（容斥原理）

传送门

code

/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
************************************************************************/

#include
#define LL long long
#define endl '\n'
using namespace std;
const int mod = 998244353, maxx = 3e5;
LL n, m, k, fac[maxx], inv[maxx], ans;
LL qpow(LL x, LL y){
    LL res = 1;
    while(y){
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void init(){
    fac[0] = 1;
    for(int i = 1; i <= maxx - 10; ++i) fac[i] = fac[i - 1] * i % mod;
    inv[maxx - 10] = qpow(fac[maxx - 10], mod - 2);
    for(int i = maxx - 11; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
LL C(int n, int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out","w", stdout);
#endif
    init();
    cin >> n >> m >> k;
    ans = C(n, m);
    for(int i = 1, fg = -1; i <= n - m + 1; ++i){
        ans = (ans + fg * C(n - m + 1, i) * C(n - i * (k + 1), n - m)) % mod;
        fg *= -1;
    };
    LL ans1 = ans; ans = 0;
    ans = C(n, m);
    for(int i = 1, fg = -1; i <= n - m + 1; ++i){
        ans = (ans + fg * C(n - m + 1, i) * C(n - i * k, n - m)) % mod;
        fg *= -1;
    }
    cout << ((ans1 - ans) % mod + mod) % mod << endl;
    return 0;
}