本地通过,洛谷RE求助
查看原帖
本地通过,洛谷RE求助
686342
Jim_Franklin楼主2024/3/31 19:30
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ri register
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
inline int rd(){
	int x=0,y=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return x*y;
}
const int N=1e6+5;
int cnt,n,m,P,p[N],X,a[N],x,y,pp[N];
int exgcd(int a,int b){if(!b){x=1;y=0;return a;}int d=exgcd(b,a%b),t=x;x=y;y=t-a/b*y;return d;}
int crt(){int res=0;for(int i=1;i<=cnt;i++)exgcd(P/p[i],p[i]),x=(x+p[i])%p[i],res=(res+P/p[i]*x%P*a[i]%P)%P;return res;}
int ksm(int x,int y,int mod){int res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res;}
int solve(int x,int p,int q){
	if(!x)return 1;int res=1;for(int i=1;i<=q;i++)if(i%p)res=res*i%q;res=ksm(res,x/p,q);
	for(int i=1;i<=x%q;i++)if(i%p)res=res*i%q;return solve(x/p,p,q)*res%q;
}
int C(int n,int m,int p,int q){
	if(n>m)return 0;int res=solve(m,p,q)*ksm(solve(n,p,q),q-q/p-1,q)%q*ksm(solve(m-n,p,q),q-q/p-1,q)%q,v=0;
	for(int i=p;i<=m;i*=p)v+=m/i;for(int i=p;i<=n;i*=p)v-=n/i;for(int i=p;i<=m-n;i*=p)v-=(m-n)/i;
	return ksm(p,v,q)*res%q;
}
signed main(){
	n=rd();m=rd();X=P=rd();
	for(int i=2;i*i<=X;i++)if(X%i==0){p[++cnt]=1;pp[cnt]=i;while(X%i==0)p[cnt]*=i,X/=i;}if(X>1)p[++cnt]=pp[cnt]=X;
	for(int i=1;i<=cnt;i++)a[i]=C(m,n,pp[i],p[i]);cout<<crt()<<'\n';
	return 0;
}

2024/3/31 19:30
加载中...