一道经典组合数学+容斥题。
题目传送门：。
题意简述：
\(p\) 个人，每个人有得分 \(a_i\)。
总得分 \(\sum a_i = s\)。 第一个人得分 \(a_1 \ge r\)。得分最高的人可以获胜，如果多个人得分最高，则等概率随机其中一个人获胜。
问第一个人获胜的概率。
题解：
第一个人要获胜，他的得分必须是最高分。
考虑枚举第一个人的得分，假设 \(a_1 = x\)。
再枚举总共有几个人得分和第一个人一样（包括第一个人），假设有 \(i\) 个。
那么剩下的 \(p - i\) 个人的得分必须满足 \(a_i < x\)，\(\sum a_i = s - ix\)。
也就是说，\(s - ix\) 个无标号小球，放进 \(p - i\) 个有标号盒子中，允许空盒子，每个盒子最多放 \(x - 1\) 个球。
经典的组合问题：\(n\) 个小球放入 \(m\) 个盒子，允许空盒子的方案数为 \(\binom{n + m - 1}{m - 1}\)。
加上了球数不能大于等于 \(x\) 的限制，考虑容斥：
枚举超过限制的盒子数 \(0 \le i \le m\)，容斥系数是 \((-1)^i\binom{m}{i}\)。
而 \(i\) 个盒子超过了限制的答案是 \(\binom{n-ix+m-i-1}{m-i-1}\)。
所以答案是 \(\sum\limits_{i=0}^{m}(-1)^i\binom{m}{i}\binom{n-ix+m-i-1}{m-i-1}\)。
总答案是 \(\sum\limits_{x=r}^{s}\sum\limits_{i=1}^{p}\binom{p}{i}\left(\sum\limits_{j=0}^{p-i}(-1)^j\binom{p-i}{j}\binom{n-ix-jx+p-i-j-1}{p-i-j-1}\right)/i\)。
当然这式子太长了，不如封装一下。注意各种组合数无意义的情况，continue掉就好了。
复杂度 \(O(p^2s)\)。
#includetypedef long long LL;const int Mod = 998244353;inline int chk(int x) { if (x < 0) x += Mod; if (x >= Mod) x -= Mod; return x; }inline int qPow(int b, int e){ int a = 1; for (; e; b = (LL)b * b % Mod, e >>= 1) if (e & 1) a = (LL)a * b % Mod; return a;}int p, s, r, c[5105][105];void Init(){ for (int i = 0; i <= 5100; ++i) c[i][0] = 1; for (int i = 0; i <= 5100; ++i) for (int j = 1; j <= i && j <= 100; ++j) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mod;}inline int Calc(int n, int m, int x){ LL S = 0; for (int i = 0; i <= m && i * x <= n; ++i) { LL s = (LL)c[m][i] * c[n - x * i + m - 1][m - 1] % Mod; S += i & 1 ? -s : s; } return (S % Mod + Mod) % Mod;}int Sum1, Sum2;int main(){ scanf("%d%d%d", &p, &s, &r); if (p == 1) return puts("1"), 0; Init(); for (int x = r; x <= s; ++x) { if (x * p < s) continue; for (int i = 1; i <= p; ++i) { if (i * x > s || (p - i) * (x - 1) + i * x < s) continue; if (i == p) { Sum2 = (Sum2 + (i * x == s ? qPow(i, Mod - 2) : 0)) % Mod; continue; } Sum2 = (Sum2 + (LL)c[p - 1][i - 1] * Calc(s - i * x, p - i, x) % Mod * qPow(i, Mod - 2)) % Mod; } } Sum1 = c[s - r + p - 1][p - 1]; printf("%lld\n", (LL)Sum2 * qPow(Sum1, Mod - 2) % Mod); return 0;}
式子也可以写成 \(p!\sum\limits_{x=r}^{s}\sum\limits_{i=1}^{p}\frac{1}{(m-i)!}\binom{n-ix-i-1}{p-i-1}\sum\limits_{j=1}^{i}\frac{(-1)^{i-j}}{(i-j)!}\cdot\frac{1}{j!\cdot j}\)。（惊了，可以卷积）
复杂度可以优化到 \(O(p\log p+sp)\)。（为什么要写