T7 The Top Scorer (CF1096E)

· · 个人记录

T7 The Top Scorer (CF1096E)

CF传送门

洛谷传送门

题意简述

小明在打比赛，包括小明自己共有 p 名选手参赛，每个人的得分是一个非负整数。最后的冠军是得分最高的人，如果得分最高的人有多个，就等概率从这些人中选一个当冠军。

现在小明已知自己的得分大于等于 r ，所有选手的得分和为 s 。所有人的得分情况随机。求小明获胜的概率，结果对 998244353 取模。

数据范围
1 \leq p \leq 100 1 \leq r,s \leq 5000
题解

思路

首先来暴力dp

涉及到最大值，因此可以让所有人都不超过某个值

设 dp[s][p][m] 表示 共有 p 人，总共 s 分，所有人的分都不超过 m的方案数

状态转移方程很好写了，考虑新加入的是得分为i的选手

dp[s][p][m]=\sum\limits_{i=0}^m dp[s-i][p-1][m]

怎么计算答案呢？

考虑到有多个人并列第一的情况，不妨枚举q人并列第一并且小明得t分，计算情况总数

当然这q个人里必须包含小明

情况总数 =\sum\limits_{t=r}^s \sum\limits_{q=1}^p \frac{1}{q} C^{q-1}_{n-1} dp[s-q*t][n-q][t-1]

别忘了答案是求概率，还得除以总数

总数怎么计算呢？

其实就是个数学问题，插板法

假设每个人的分数为 a_i(a_i \geq 0)，小明分数为 k(k \geq r)

那么就是求 a_1+a_2+...+a_{p-1}+k=s 的解集个数

转化成正整数

(a_1+1)+(a_2+1)+...+(a_{p-1}+1)+[k-(r-1)]=s+(p-1)-(r-1)

即求 b_1+b_2+...+b_p=s+p-r (b_i \geq 1) 的解集个数

就是插板法，在 s+p-r 个 1 间插入 p-1 个 + 号，分成 p 个数

即共 C_{s+p-r-1}^{p-1} 种方案

ans= \frac{\sum\limits_{t=r}^s \sum\limits_{q=1}^p \frac{1}{q} C^{q-1}_{n-1} dp[s-q*t][n-q][t-1]} {C^{s+p-r-1}_{p-1}}

写了这么多，累死我了 该出答案了吧？

木有

会发现这是 O(rsp) 的，3s根本跑不过去

那么接下来的事情就与dp无关了

看看 ans 那个式子，会发现其实我们只会用到 O(sp) 个数

所以能不能不经过递推，直接把单个dp算出来呢？

可以。

怎么去算呢？ 直接算是不好操作的，“不超过 $m$ 个” 不好处理 所以不妨来考虑容斥原理 先随便投，$C^{s+p-1}_{p-1}

然后来考虑至少有 i 个篮子里超过 m 个球的情况数

首先要选出这 i 个篮子，C^i_p

这时候又可以来用插板法了，用 a 来表示这 i个选出的篮子，用 b 表示剩下的

a_1+a_2+...+a_i+b_1+b_2+..+b_{p-i}=s (a_i > m,b_i \geq 0) (a_1-m)+(a_2-m)+...+(a_i-m)+(b_1+1)+(b_2+1)+..+(b_{p-i}+1) =s-im+(p-i) =s-i(m+1)+p

记S_i=C^{p-1}_{s+p-i(m+1)-1}

刚开始选出来的 C^i_p 其实就是 S_0

最后来容斥，

dp[s][p][m] =S_0-S_1+S_2-S_3+...+(-1)^mS_m =\sum\limits_{i=0}^m (-1)^iS_i

把 S_i 替换掉

dp[s][p][m]=\sum\limits_{i=0}^m (-1)^iC^{p-1}_{s+p-i(m+1)-1}

还有ans的算法

ans= \frac{\sum\limits_{t=r}^s \sum\limits_{q=1}^p \frac{1}{q} C^{q-1}_{n-1} dp[s-q*t][n-q][t-1]} {C^{s+p-r-1}_{p-1}}

时间复杂度最大 O(p^2s)

做法

对于每一个要求的dp值，按照公式计算即可

组合数逆元啥的很基础了

还需要解释吗？

注意事项

· 注意特判，尤其注意 \leq 0 的

· long long...

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long P=110,N=5005;
long long mod=998244353;
long long mul[P+N],inv[P+N];
long long p,s,r,ans=0;

long long C(long long m,long long n){
    if(m<0 || n<0 || m-n<0) return 0;//必要的，因为会有负数 
    if(m*n==0) return 1;//特判 
    return mul[m]*inv[n]%mod*inv[m-n]%mod;
}
long long ksm(long long a,long long x){
    long long sum=1;
    while(x){
        if(x&1) sum=sum*a%mod;
        a=a*a%mod,x>>=1;
    }
    return sum;
}
long long dp(long long s,long long p,long long m){
    if(s==0 && p==0) return 1;//奇怪的特判 
    long long tot=0;
    for(long long i=0;i<=p;i++){
        long long tmp=C(p,i)*C(s+p-1-i*(m+1),p-1)%mod;
        tot= (i%2)?(tot-tmp+mod)%mod:(tot+tmp)%mod;
    }
    return tot;
}
int main(){
    scanf("%lld%lld%lld",&p,&s,&r);
    mul[0]=inv[0]=1;
    for(long long i=1;i<=p+s;i++) mul[i]=mul[i-1]*i%mod;
    inv[p+s]=ksm(mul[p+s],mod-2);
    for(long long i=p+s-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
    //预处理阶乘和逆元
    for(long long t=r;t<=s;t++)
        for(long long q=1;q<=p;q++)
            ans=(ans+C(p-1,q-1)*ksm(q,mod-2)%mod*dp(s-q*t,p-q,t-1)%mod)%mod;
    //公式计算答案
    ans=(ans*ksm(C(s-r+p-1,p-1),mod-2))%mod;//最后要除以总数 
    printf("%lld",ans);
}