$Exlucas$

本来以为自己能记住就不写了，然而事实证明还是要推一推柿子的。

求$C_{n}^{m}\%P$。

根据$CRT$：

$P=p_i^{k_i}...$

求出$C_{n}^{m} \equiv a_i(\% p_i^{k_i})$里每个$a_i$，$CRT$合并即可。

因为只有在互质时才能出逆元，可以考虑将阶乘中的所有$p_i$提出来。

变成$fac(n)=fac(n/p)*({\prod_{i=1\&\&i\%p!=0}^{pk}})^{\frac{n}{pk}}*({\prod_{i=1\&\&i\%p!=0}^{n\%pk}})$。

然后求子问题$\frac{n!}{p^{x}}\% p^{k}$

$fac(n)=fac(n/p)*(\prod _{i=1\&\&i\%p!=0}^{pk})^{\frac{n}{pk}}*(\prod _{i=1\&\&i\%p!=0}^{n\%pk})$

递归求解，即一层层提出$p$，意为先提出所有作为$p^1$的$p$，再提出$p^2$的$p$等等。

后面是在这层的类阶乘的东西有循环节及余项。

例题：礼物

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<map>
 5 #define LL long long
 6 using namespace std;
 7 namespace EXLUCAS{
 8     map<int ,int >phi;
 9     int _p[30]={},_pk[30]={},cnt;
10     inline void init(int Mod){
11         cnt=0;int x=Mod,t=1;
12         for(int i=2,t1,t2;i<=sqrt(x);++i)
13             if(x%i==0){
14                 x/=i;t1=i;t2=i-1;
15                 while(x%i==0)x/=i,t1*=i,t2*=i;
16                 _p[++cnt]=i;_pk[cnt]=t1;phi[t1]=t2;
17                 t*=phi[t1];
18             }
19         if(x>1)_p[++cnt]=x,_pk[cnt]=x,phi[x]=x-1,t*=phi[x];
20         phi[Mod]=t;
21         return ;
22     }
23     inline LL qpow(LL a,LL b,const int &mod){
24         LL res=1LL;a%=mod;
25         for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
26         return res%mod;
27     }
28     inline LL inv(int x,int Mod){
29         return qpow(x,phi[Mod]-1,Mod);
30     }
31     inline LL fac(int n,int pi,int pk){
32         if(!n)return 1;
33         LL res=1LL;
34         for(int i=2;i<pk;++i)if(i%pi)res=res*i%pk;
35         res=qpow(res,n/pk,pk);
36         for(int i=2;i<=n%pk;++i)if(i%pi)res=res*i%pk;
37         return res*fac(n/pi,pi,pk)%pk;
38     }
39     inline LL C(int n,int m,int pi,int pk){
40         LL fz=fac(n,pi,pk),fm1=fac(m,pi,pk),fm2=fac(n-m,pi,pk);
41         int k=0;
42         for(int i=n;i;i/=pi)k+=i/pi;
43         for(int i=m;i;i/=pi)k-=i/pi;
44         for(int i=n-m;i;i/=pi)k-=i/pi;
45         return fz*inv(fm1,pk)%pk*inv(fm2,pk)%pk*qpow(pi,k,pk)%pk;
46     }
47     inline LL CRT(int ai,int pk,int Mod){
48         return inv(Mod/pk,pk)*(Mod/pk)%Mod*ai%Mod;
49     }
50     inline LL exlucas(int n,int m,const int &Mod){
51         if(n<m)return 0;
52         if(!m)return 1LL;
53         LL res=0;
54         for(int i=1;i<=cnt;++i)res=(res+CRT(C(n,m,_p[i],_pk[i]),_pk[i],Mod))%Mod;
55         return res%Mod;
56     }
57 }
58 using namespace EXLUCAS;
59 int n,m,P;
60 int w[10];LL sumw=0;
61 LL ans=1LL;
62 int main(){
63     scanf("%d%d%d",&P,&n,&m);
64     for(int i=1;i<=m;++i){
65         scanf("%d",&w[i]);
66         sumw+=w[i];
67     }
68     if(sumw>n){puts("Impossible");return 0; }
69     init(P);
70     for(int i=1;i<=m;++i){
71         ans=ans*exlucas(n,w[i],P)%P;
72         n-=w[i];
73     }
74     printf("%lld\n",ans%P);
75     return 0;
76 }

View Code