题目地址：洛谷CF1096E
本场AC数最少 （最难） 的题目
题目大意：给出三个数p , s，r，表示有p人，每个人都有一个非负得分，所有人的得分和为s，Hasan的得分至少为r，求Hasan是第一的概率（得分相同的人名次是等概率分布）
数据范围： \(1 \leq p \leq 100,0 \leq r \leq s \leq 5000\)
注意输出有一个整数化处理：若 \(ans = \frac{P}{Q}\) ，输出 \(P \times inv_Q(mod\ 998244353)\) ，这里的 \(inv_Q(mod\ 998244353)\) 指的是 \(Q\) 的模 \(998244353\) 的乘法逆元
容斥原理
首先解决一个问题：有 \(p\) 人，所有人的得分和为 \(s\) 且所有人的得分均小于等于 \(m\) ，有多少种情况？
根据容斥原理，答案为：
\[\sum_{i=0}^{p}\ (-1)^i\ C_{p}^{i}\ C_{s+p-1-i(m+1)}^{p-1}\]
有了这个公式，接下来就是好办了：枚举 Hasan 的得分和与 Hasan 得分相同的人数，算出每一种情况的总数之和，最后除以所有可能的情况即为 \(ans\)
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10006, M = 106, P = 998244353;
int jc[N], jcinv[N];
inline int ksm(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (ll)ans * a % P;
a = (ll)a * a % P;
b >>= 1;
}
return ans;
}
inline int C(int b, int a) {
if (a == b) return 1;
if (a < 0 || a > b) return 0;
return (ll)jc[b] * jcinv[a] % P * jcinv[b-a] % P;
}
inline int g(int s, int p, int x) {
int ans = 0;
for (int i = 0; i <= p; i++)
ans = (ans + (ll)((i & 1) ? P - 1 : 1) * C(p, i) % P * C(s + p - 1 - i * (x + 1), p - 1) % P) % P;
return ans;
}
inline int inv(int x) {
return (ll)jc[x-1] * jcinv[x] % P;
}
int main() {
jc[0] = 1;
for (int i = 1; i <= 10000; i++)
jc[i] = (ll)jc[i-1] * i % P;
jcinv[10000] = ksm(jc[10000], P - 2);
for (int i = 10000; i; i--)
jcinv[i-1] = (ll)jcinv[i] * i % P;
int p, s, r;
cin >> p >> s >> r;
int ans = 0;
for (int i = r; i <= s; i++)
for (int j = 1; j <= p; j++)
ans = (ans + (ll)C(p - 1, j - 1) * inv(j) % P * g(s - i * j, p - j, i - 1) % P) % P;
cout << ((ll)ans * ksm(C(s - r + p - 1, p - 1), P - 2) % P + P) % P << endl;
return 0;
}