不知为何就挂了,求助dalao(顺便求一些码风建议)
查看原帖
不知为何就挂了,求助dalao(顺便求一些码风建议)
670455
ska_0x08楼主2022/8/5 14:17
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct T
{
	int num,p;	
};
vector <T> p;
ll anns=0,n,m,P,fac[1000010],cnt=0;
void exgcd(ll a,ll b ,ll &x, ll &y)//扩欧 
{
	if(b==0){x=1,y=0;return;}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
	return ;
}
void pre()//分解p 
{
	int res=P;
	for(int i=2;i<=sqrt(P);i++)
	{
		if(res<i) break;
		if(res%i==0)
		{
			int cnt=1;
			while (res%i==0){cnt*=i;res/=i;}
			p.push_back({i,cnt});		
		}
	}
	if(res>1) p.push_back({res,res});
}

ll quick_pow(ll a,ll b,ll mod)//快速幂 
{
	if(b==0) return 1;
	if(b==1) return a%mod;
	if(b&1)  return a%mod*quick_pow(a,b-1,mod)%mod;
	ll cun=quick_pow(a,b/2,mod)%mod;
	return cun*cun%mod;
}

void prefac(ll p,ll pe)//预处理 
{
	fac[0]=1;
	for(int i=1;i<=pe;i++)
	{
		if(i%p==0) fac[i]=fac[i-1];
		else fac[i]=fac[i-1]*i;
	}
	return ;
}

ll preres(ll n,ll p,ll pe)//处理不含p的乘积 
{
	ll ans=1;
	if(n==0) {return ans;}
	return preres(n/pe,p,pe)%pe*quick_pow(fac[pe-1],n/pe,pe)*fac[n%pe]%pe;
}

ll prepow(ll n,ll m,ll p)//处理每一次的指数 
{
	ll ans=0;
	for(int i=n;i;i/=p)
	ans+=i/p;
	for(int i=m;i;i/=p)
	ans-=i/p;
	for(int i=n-m;i;i/=p)
	ans-=i/p;
	return ans;
}

ll inv(ll a,ll b)//求逆元 
{
	ll ans,p;
	exgcd(a,b,ans,p);
	return (ans%b+b)%b;
}
void crt(ll m,ll a1)//合并答案 
{
	ll Mul=P;
	ll pre=Mul/m;
	ll nipre;
	nipre=inv(pre,m);
	anns=(anns+a1%Mul*pre%Mul*nipre)%Mul; 
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&P);  //n!/(m!(n-m)!)
	pre();
	for(int i=0;i<p.size();i++)//枚举约数 
	{
		ll mo=p[i].num,pe=p[i].p;
		prefac(mo,pe);
		ll resn=preres(n,mo,pe),resm=preres(m,mo,pe),resM=preres(n-m,mo,pe);//求n! m! (n-m)!中不含mo的部分的乘积 
		ll ans;
		ll nim,niM;
		nim=inv(resm,pe);
		niM=inv(resM,pe);//求逆元
		 
		 
		ans=quick_pow(mo,prepow(n,m,mo)/*mo的次数*/,pe)*resn%pe*nim%pe*niM%pe;
		
		crt(pe,ans);//合并答案 
	}
	printf("%lld",anns);
	return 0;
}
2022/8/5 14:17
加载中...