题解：P14686 [ICPC 2025 Yokohama R] Charity Raffle

· · 题解

我们发现有且仅有如下情况不合法：

容易想到计算 \sum [A] - \sum [A \wedge (\neg B \vee \neg C)]。

前面一项考虑容斥，钦定 i 个值大于 m，然后使用插板法，答案即为

\sum_{i = 0}^{n} (-1)^i {n \choose i}{k - i(m + 1) + n - 1 \choose n - 1}

后面一项考虑先枚举最大值 i 和其位置 p，那么不满足条件要求 [1, p) 的值都属于 [0, i - 1]，(p, n] 的值都属于 [0, i - 2]，依然容斥，答案即为

\begin{aligned} &\sum_{i = 1}^{m} \sum_{p = 1}^{n} \sum_{x = 0}^{p - 1} (-1)^x {p - 1 \choose x} \sum_{y = 0}^{n - p} (-1)^y {n - p \choose y} {k - xi - y(i + 1) - i + n - 2 \choose n - 2}\\ &= \sum_{i = 1}^{m} \sum_{s = 0}^{n - 1} (-1)^{s} {n \choose s + 1} \sum_{x = 0}^{s} {k - si + x - i + n - 2 \choose n - 2}\\ &= \sum_{i = 1}^{m} \sum_{s = 0}^{n - 1} (-1)^{s} {n \choose s + 1} ({k - si + s - i + n - 1 \choose n - 1} - {k - si - i + n - 2 \choose n - 1})\\ \end{aligned}

注意到上式不为 0 需要 k - si + s - i \geq 0 或 k - si - i - 1 \geq 0，所以 si 是 \mathcal{O}(k) 的，直接枚举时间复杂度 \mathcal{O}(k)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 1e6 + 10, maxk = 1e6 + 10, mod = 998244353;

int n, k, m, res = 0;
int fac[(maxn << 1) + maxk], ifac[(maxn << 1) + maxk];

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x x, Tp_y y){
    return x += y, x >= mod ? x -= mod : x;
}

template<typename Tp_x, typename Tp_y>
inline int self_mod_add(Tp_x &x, Tp_y y){
    return x = mod_add(x, y);
}

template<typename Tp, typename... Arg>
inline int mod_add(Tp x, Arg ...args){
    return x += mod_add(args...), x >= mod ? x -= mod : x;
}

inline long long ksm(long long a, long long b){
    long long res = 1;
    for (;b; b & 1 && (res = res * a % mod), a = a * a % mod, b >>= 1);
    return res;
}

inline long long inv(long long x){
    return ksm(x, mod - 2);
}

inline long long c(int n, int m){
    return n >= m && m >= 0 ? (long long)fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0;
}

int main(){
    scanf("%d %d %d", &n, &k, &m), fac[0] = 1;
    for (int i = 1; i <= k + (n << 1); i++){
        fac[i] = (long long)fac[i - 1] * i % mod;
    }
    ifac[k + (n << 1)] = inv(fac[k + (n << 1)]);
    for (int i = k + (n << 1) - 1; ~i; i--){
        ifac[i] = (long long)ifac[i + 1] * (i + 1) % mod;
    }
    for (int i = 0; i <= n && i * (m + 1) <= k; i++){
        const int val = c(n, i) * c(k - i * (m + 1) + n - 1, n - 1) % mod;
        self_mod_add(res, i & 1 ? mod - val : val);
    }
    for (int i = 1; i <= m; i++){
        for (int s = 0; s + 1 <= n && (k - s * i + s - i >= 0 || k - s * i - i - 1 >= 0); s++){
            const int val = c(n, s + 1) * mod_add(c(k - s * i + s + n - 1 - i, n - 1), mod - c(k - s * i + n - 2 - i, n - 1)) % mod;
            self_mod_add(res, s & 1 ? val : mod - val);
        }
    }
    printf("%d", res);

return 0;
}