[CRT][中国剩余定理]膜法

容易发现是杨辉三角形，第i个数的贡献为c(n-1,i-1);但是由于mod数不是质数，所以考虑用CRT来做。先拆mod数，然后在求组合数的过程中将每个数拆成a*pi^ci的形式，非常感谢dmsdalao对我中国剩余定理的指导。 关于CRT详见 http://blog.csdn.net/qq_36993218/article/details/60956475

---

#include<cstdio> #include<algorithm> #include<iostream> #define ll long long #define Pair pair<ll,ll> using namespace std; int n,K; inline int read() { char c; bool flag=false; while((c=getchar())>'9'||c<'0') if(c=='-') flag=true; int res=c-'0'; while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0'; return flag?-res:res; } const int N=4*1e5+7; int tot,a[N]; ll p[N],c[N],m[N],M[N],H[N],ans[N]; inline ll ksm(ll a,int b) { ll res=1; while(b) { if(b&1) res=res*a; a=a*a; b>>=1; } return res; } inline ll ksm(ll a,int b,int pyz) { ll res=1; while(b) { if(b&1) res=res*a%pyz; a=a*a%pyz; b>>=1; } return res; } inline ll inv(ll a,int x) { return ksm(a,(p[x]-1)*m[x]/p[x]-1,m[x]); } Pair fac[N]; inline Pair div(Pair A,Pair B,int x) { return Pair(A.first*inv(B.first,x)%m[x],A.second-B.second); } inline Pair mul(Pair A,Pair B,int x) { return Pair(A.first*B.first%m[x],A.second+B.second); } inline Pair C(int n,int m,int x) { return div(fac[n],mul(fac[m],fac[n-m],x),x); } inline Pair trans(int i,int x) { Pair res=Pair(0,0); while(i%p[x]==0&&i) { i/=p[x]; res.second++; } res.first=i; return res; } inline ll get_num(Pair x,int i) { return (ll)x.first*ksm(p[i],x.second,m[i])%m[i]; } inline void solve(int now) { fac[0]=Pair(1,0); for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],trans(i,now),now); for(int i=1;i<=n;++i) ans[now]=(ans[now]+get_num(mul(trans(a[i],now),C(n-1,i-1,now),now),now))%m[now]; } int main() { freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); n=read(); K=read(); for(int i=1;i<=n;++i) a[i]=read(); int tmp=K; for(int i=2;i<=tmp;++i) if(tmp%i==0) { p[++tot]=i; while(tmp%i==0) { c[tot]++; tmp/=i; } } for(int i=1;i<=tot;++i) { m[i]=ksm(p[i],c[i]); M[i]=K/m[i]; H[i]=inv(M[i],i); solve(i); } ll Ans=0; for(int i=1;i<=tot;++i) Ans=(Ans+(ll)ans[i]*M[i]%K*H[i]%K)%K; cout<<Ans; }