魔法【省选模拟赛】

求组合数(模数非质数)

Posted by yjjr's blog on March 16, 2018

标签:组合数

题目

这里写图片描述

分析

发现答案显然是组合数

难点转化为怎样求数据范围内的组合数(且模数不为质数)

我们可以想到分解质因数的方法

上面的质因数个数减去下面的质因数个数,剩下的乘起来,就不用求再取模了

考虑怎样优化

我们可以先求出模数的质因数,再考虑求组合数过程中的分解质因数

如果质因数和模数的质因数一样,因为不互质所以不存在逆元,把它记录下来,最后用快速幂乘起来就好了

否则可以用这个公式直接求逆元

因为模数p并不大,所以可以直接暴力求phi

其实这题也可以直接CRT(中国剩余定理)合并解决

code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
const int maxn=1e6+6;
int n,x,p,prime[maxn],cnt,Num[maxn],ans;
inline int qpow(int x,int y){
	int re=1;
	while(y){
		if(y&1)re=(ll)re*x%p;
		y>>=1,x=(ll)x*x%p;
	}
	return re;
}
void Pre(int x){
    for(int i=2;i*i<=x;i++)
		if(!(x%i)){
            prime[++cnt]=i;
            while(!(x%i))x/=i;
        }
    if(x>1)prime[++cnt]=x;
}
inline int getgcd(int x,int y){return !x?y:getgcd(y%x,x);}
inline int phi(int x){int re=0;rep(i,1,x-1)if(getgcd(i,x)==1)re++;return re;}
inline int Add(int x,int P){
    if(!x||x==1)return x;
    rep(i,1,cnt){    
        while(!(x%prime[i])){
            x/=prime[i];
            Num[prime[i]]+=P;
        }
        if(x==1)break;
    }
    return x;
}
int main()
{      
	//freopen("magic.in","r",stdin);
	//freopen("magic.out","w",stdout);
    n=read(),p=read();
    Pre(p);
	int Phi=phi(p),C=1,record=1;
    rep(i,1,n){
        x=read();
        ans=(ans+(ll)record*x%p)%p;
        if(i==n)break;
        C=(ll)C*Add(n-i,1)%p*qpow(Add(i,-1),Phi-1)%p;
        record=C;
        rep(j,1,cnt)record=(ll)record*qpow(prime[j],Num[prime[j]])%p;
    }
   	cout<<ans<<endl;
   	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr