自动搬运

查看原文

来自洛谷，原作者为

	ztz11 **

搬运于2025-08-24 22:05:57，当前版本为作者最后更新于2018-11-04 11:49:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

比较良心的部分分（50pts）
前30分可以暴力
另20分可以递推
对于这道题，化简下来，就是$C_{minx+1}^n+C_{minx+2}^n+...+C_n^n$
(n为合格的水军数量，minx为最少需要的水军数量（因为要去掉最高分，所以我们要+1）)
然后对于p=质数的情况，lucas定理即可
p!=质数的话用exlucas就行
当然，据说有人暴力能水不少分？tql！（可能是我数据出水了）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j 
#define int long long
using namespace std;
int n1,m1,p,nl[100005],t;
int pf[10]={0,1,10,15,25,40,55,75,100};
int pow(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1)
        {
            res=res*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int exgcd(int a,int b,int& x,int& y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    int res=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return res;
}
int reverse(int a,int p)
{
    int x,y;
    exgcd(a,p,x,y);
    return (x%p+p)%p;
}
int C(int n,int m,int p)
{
    if(m>n)
    {
        return 0;
    }
    int res=1,i,a,b;
    for(i=1;i<=m;i++)
    {
        a=(n+1-i)%p;
        b=reverse(i%p,p);
        res=res*a%p*b%p;
    }
    return res;
}
int Lucas(int n,int m,int p)
{
    if(m==0)
    {
        return 1;
    }
    return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int cal(int n,int a,int b,int p)
{
    if(!n)
    {
        return 1;
    } 
    int i,y=n/p,tmp=1;
    for(i=1;i<=p;i++)
    {
        if(i%a)
        {
            tmp=tmp*i%p;
        }
    }
    int ans=pow(tmp,y,p);
    for(i=y*p+1;i<=n;i++)
    {
        if(i%a)
        {
            ans=ans*i%p;
        } 
        
    } 
    return ans*cal(n/a,a,b,p)%p;
}
int multiLucas(int n,int m,int a,int b,int p)
{
    int i,t1,t2,t3,s=0,tmp;
    for(i=n;i;i/=a)
    {
        s+=i/a;
    }
    for(i=m;i;i/=a)
    {
        s-=i/a;
    }
    for(i=n-m;i;i/=a)
    {
        s-=i/a;
    }
    tmp=pow(a,s,p);
    t1=cal(n,a,b,p);
    t2=cal(m,a,b,p);
    t3=cal(n-m,a,b,p);
    return tmp*t1%p*reverse(t2,p)%p*reverse(t3,p)%p;
}
int exLucas(int n,int m,int p)
{
    int i,d,c,t,x,y,q[100],a[100],e=0;
    for(i=2;i*i<=p;i++)
    {
        if(p%i==0)
        {
            q[++e]=1;
            t=0;
            while(p%i==0)
            {
                p/=i;
                q[e]*=i;
                t++;
            }
            if(q[e]==i)
            {
                a[e]=Lucas(n,m,q[e]);
            }
            else
            {
                a[e]=multiLucas(n,m,i,t,q[e]);
            }
        }
    }
    if(p>1)
    {
    	e++;
        q[e]=p;
        a[e]=Lucas(n,m,p);
    }
    for(i=2;i<=e;i++)
    {
        d=exgcd(q[1],q[i],x,y);
        c=a[i]-a[1];
        if(c%d)
        {
            exit(-1);
        }
        t=q[i]/d;
        x=(c/d*x%t+t)%t;
        a[1]=q[1]*x+a[1];
        q[1]=q[1]*q[i]/d;
    }
    return a[1];
}
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}
bool cmp(int lk,int kl)
{
	return lk<kl;
}
void solve()
{
	n1=rd();
	m1=rd();
	p=rd();
//	scanf("%lld%lld%lld",&n,&m,&p);
	for(rii=1;i<=n1;i++)
	{
		nl[i]=rd();
//		scanf("%lld",&nl[i]);
	}
	sort(nl+1,nl+n1+1,cmp);
	int minx=10,jsq=0;
	for(rii=1;i<=m1;i++)
	{
		int val;
		val=rd();
//		scanf("%lld",&val);
		minx=min(minx,val);
		jsq+=pf[val];
	}
	jsq-=pf[minx];
	int cha=(m1-1)*71-jsq;
	int mins=cha/29;
	if(mins*29<cha)
	{
		mins++;
	}
	if(cha<=0)
	{
		mins=0;
	}
	int ans=0;
	int zx;
	zx=rd();
//	scanf("%lld",&zx);
	int cnt=n1;
	for(rii=1;i<=n1;i++)
	{
		if(nl[i]<zx)
		{
			cnt--;
		}
		else
		{
			break;
		}
	}
	n1=cnt;
	for(rii=mins+1;i<=n1;i++)
	{
		ans+=exLucas(n1,i,p);
		ans%=p;
	}
    printf("%lld\n",ans);
}
signed main()
{
// 	freopen("pf10.in","r",stdin);
// 	freopen("pf10.out","w",stdout);
    scanf("%lld",&t);
    for(rii=1;i<=t;i++)
    {
    	solve();
	}
}