CF1096E The Top Scorer
题意
(~~~~) 给出数列 (p) 个人各自的 (a_i) 表示得分, (sum a_i=s) ，求在第一个数 (geqslant r) 的情况下，它是最大值的概率。若有其他数与它的值相同，最大值会认为是等概率选择了其中的一个.（即若不包括它在内有 (k) 个最大值，则概率 (/k) ）
题解
(~~~~) 不会吧不会吧，这题CF上只有2500。受到专题训练影响直接想 ( exttt{DP}) ，然后发现时空都会爆，状态具体怎么定义出来都成问题。
(~~~~) 否决了概率 ( exttt{DP}),那现在我们只能直接计算概率了。
(~~~~) 总的方案数很好求，是：
(~~~~) 解释： 上式可以用插板法可以推出，相当于把 (s-r) 分（第一个人必须有 (r)）分配给 (p) 个人。但注意分数可以是 (0) ，所以每个人插板后会有新空隙。
(~~~~) 所以我们来求合法的方案数。
(~~~~) 枚举有 (i) 人（包括 (1) 自己在内）同最高分 (x) 。那我们有 (egin{pmatrix}p-1\i-1end{pmatrix}) （ (1) 必定要被选）种选人方案。
(~~~~) 接下来是求另一个子问题： (p-i) 人分 (s-ix) 分，每人可以分到 ([0,x-1]) 分的方案数。
(~~~~) 为方便，下文令:(n=s-ix,m=p-i).
(~~~~) 方案数无法直接正面求到，那我们是否可以考虑反面求呢？
(~~~~) 考虑优先给 (m) 个人都安排上 (x) 分，那这样就可以求出 (m) 个人都不满足条件的方案数。以此类推算出([0,m-1]) 时的方案数(dotsdots)了吗？
(~~~~) 并不是的，我们发现在求 (m-1) 人不合法时，是包括 (m) 人合法的情况的，也就是说我们每次求出来的应该是：至少 (k) 个人不合法的方案数。
(~~~~) 等等，提到了至少？那我们就自然而然想到容斥了。
(~~~~) 考虑当至少有 (kin[0,m]) 人不合法时的方案数：
- 有容斥系数：((-1)^k imesegin{pmatrix}m\kend{pmatrix}) ;
- 综合之前的策略，有答案：(egin{pmatrix}n-kx+m-k-1\kend{pmatrix}) .
(~~~~) 因此这个子问题的答案是：
(~~~~) 综上，总的答案就是：
(~~~~) 但这只是算到了合法方案数，而当 (i) 人同分时，概率会变为原式的 (dfrac{1}{i}) ，因此在求答案时要在上式每次 ( imes dfrac{1}{i}) .
(~~~~) 此外还要注意当 (i=p) 时需要特判 (ix=s) 是否成立，否的话答案为 (0) ，否则答案为 (1) (记得这是方案数，最后还是要 ( imes dfrac{1}{i}))
(~~~~) 最后除以总方案数就是概率了。
(~~~~) 另外算一下 ((n-kx+m-k-1)_{max}) 就会发现组合数底数要递推到 (5099) 而不是 (5000).
代码
(由于改组合数范围的时候修改借鉴了神兔的代码，所以可能会有亿点点像)
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const ll MOD=998244353;
ll C[5105][5105];//C[i][j]:j选i
ll p,s,r;
inline ll qpow(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%MOD;
b>>=1;
a=a*a%MOD;
}
return ret;
}
ll calc(ll n,ll m,ll x)//子问题求解
{
ll ret=0;
for(ll k=0;k<=m&&x*k<=n;k++)
{
ll tmp=C[k][m]*C[m-1][n+m-1-k*x]%MOD;
ret+=(k&1)?-tmp:tmp;
}
return ((ret%MOD)+MOD)%MOD;
}
int main() {
C[0][0]=1;
for(ll i=1;i<=5100;i++)
{
C[i][i]=C[0][i]=1;
for(ll j=1;j<=i;j++) C[j][i]=(C[j-1][i-1]+C[j][i-1])%MOD;
}
ll ans=0;
scanf("%lld %lld %lld",&p,&s,&r);
for(ll x=r;x<=s;x++)
{
for(ll i=1;i<=p;i++)
{
if(i==p) (ans+=(i*x==s?qpow(i,MOD-2):0))%=MOD;//特判 i=p
else (ans+=(C[i-1][p-1]*calc(s-i*x,p-i,x)%MOD*qpow(i,MOD-2)%MOD))%=MOD;
}
}
printf("%lld",ans*qpow(C[p-1][s-r+p-1],MOD-2)%MOD);
return 0;
}