P4993 评分系统题解

WhitD · 2023-09-28 17:04:10 · 题解

思路

首先肯定要求出为了达到黑题的要求（评分 \ge71），我们最少需要请多少水军。

设水军人数为 x，谷民人数为 m，谷民打的总分为 sum，最低分为 min，自然可列出下式：

\frac{sum-min+100(x-1)}{m-1+x-1}\ge71

关于为什么是 (x-1)：由于我们除了去掉一个最低分以外，还会去掉一个最高分，水军打的一定是最高分（100），所以算的时候直接减去就可以了。

化简后得：

x\ge\frac{71m-sum+min-42}{29}

我们所求的是最小值，即：

x=\max(1,\lceil\frac{71m-sum+min-42}{29}\rceil)

关于为什么要对 1 取 \max，是因为等式右边可能是负数，我们总不能对负数做组合数计算吧。

考虑选取的方案数，设可以做题的水军人数为 cnt，最少选取 x 人，方案数为 cnt\choose x，当然我们也可以多选，最多可以把 cnt 个人都选上，因此总方案数为：

\sum_{i=x}^{cnt}{cnt\choose i}

模数范围比较小，模数是质数的情况需要用普通卢卡斯定理解决（用扩展卢卡斯定理会 TLE on #4，比较神秘），笔者就是在这里卡了好长时间（两页提交记录）。

不是质数的情况用扩展卢卡斯定理解决就可以了。

(如果你还不了解卢卡斯定理，点这里)。

AC 代码

#include<iostream>
using namespace std;
inline int _min(int a,int b){return (a<b)?a:b;}
inline int _max(int a,int b){return (a>b)?a:b;}
inline int _ceil(double x){return (int(x)==x)?int(x):(int)(x+1);}
inline void exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return ;
    }
    exgcd(b,a%b,y,x),y-=x*(a/b);
}
inline int inv(int v,int p)
{
    register int x,y;
    exgcd(v,p,x,y);
    return (x%p+p)%p;
}
inline int qkpow(int a,int b,int p)
{
    register int res=1;
    while(b)
        res=(b&1)?res*a:res,a=a*a%p,b>>=1;
    return res%p;
}
inline int fac(int n,int pi,int pk)
{
    if(!n) 
        return 1;
    register int ans=1,i=2;
    for(i=2;i<pk;i++) 
        ans=(i%pi)?ans*i%pk:ans;
    ans=qkpow(ans,n/pk,pk);
    for(i=2;i<=n%pk;i++) 
        ans=(i%pi)?ans*i%pk:ans;
    return ans*fac(n/pi,pi,pk)%pk;
}
inline int l(int n,int m,int pi,int pk)
{
    register int ind=0,i=0;
    for(i=n;i;i/=pi) 
        ind+=i/pi;
    for(i=m;i;i/=pi) 
        ind-=i/pi;
    for(i=n-m;i;i/=pi) 
        ind-=i/pi;
    return fac(n,pi,pk)*inv(fac(m,pi,pk),pk)%pk*inv(fac(n-m,pi,pk),pk)%pk*qkpow(pi,ind,pk)%pk;
}
inline int exlucas(int n,int m,int p)
{
    register int tmp=p,ans=0,pk=1;
    for(register int i=2;i*i<=tmp;++i)
    {
        if(!(tmp%i))
        {
            pk=1;
            while(!(tmp%i)) 
                tmp/=i,pk*=i;
            ans=(ans+l(n,m,i,pk)*inv(p/pk,pk)%p*p/pk%p)%p;
        }
    }
    return (tmp>1)?(ans+l(n,m,tmp,tmp)*inv(p/tmp,tmp)%p*p/tmp%p)%p:ans%p;
}
inline int C(int n,int m,int p)
{
    if(m>n)
        return 0;
    register int res=1,i,a,b;
    for(i=1;i<=m;++i)
        a=(n+1-i)%p,b=inv(i%p,p),res=res*a%p*b%p;
    return res;
}
inline int lucas(int n,int m,int p)
{
    return (!m)?1:(lucas(n/p,m/p,p)*C(n%p,m%p,p))%p;
}
inline int is_p(int x)
{
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
            return 0;
    return 1;
}
int T,n,m,p,s[100005],mn,sum,x,k,cnt,ans,i,t,score[10]={0,1,10,15,25,40,55,75,100};
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--)
    {
        ans=sum=cnt=0,mn=100005;
        cin>>n>>m>>p;
        for(i=1;i<=n;++i)
            cin>>s[i];
        for(i=1;i<=m;++i)
            cin>>t,mn=_min(mn,score[t]),sum+=score[t];
        sum-=mn;
        x=_max(1,_ceil((71.0*m-sum-42.0)/29.0));
        cin>>k;
        for(i=1;i<=n;++i)
            cnt+=(s[i]>=k);
        if(is_p(p))
            for(x;x<=cnt;++x)
                ans=(ans+lucas(cnt,x,p));
        else
            for(x;x<=cnt;++x)
                ans=(ans+exlucas(cnt,x,p));
        cout<<(ans%p)<<'\n';
    }
    return 0;
}

P4993 评分系统 题解

思路

AC 代码

P4993 评分系统题解