标签：组合数
题目
分析
发现答案显然是组合数
难点转化为怎样求数据范围内的组合数（且模数不为质数）
我们可以想到分解质因数的方法
上面的质因数个数减去下面的质因数个数，剩下的乘起来，就不用求再取模了
考虑怎样优化
我们可以先求出模数的质因数，再考虑求组合数过程中的分解质因数
如果质因数和模数的质因数一样，因为不互质所以不存在逆元，把它记录下来，最后用快速幂乘起来就好了
否则可以用这个公式直接求逆元\(x^{-1}\mod p=qpow(x,\phi(p)-1)\)
因为模数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;
}
