BZOJ_2142_礼物_扩展lucas+组合数取模
Description
一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。
Input
输入的第一行包含一个正整数P，表示模；第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。
Output
若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。
Sample Input
100
4 2
1
2
Sample Output
12
【样例说明】
下面是对样例1的说明。
以“/”分割，“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下：
1/23 1/24 1/34
2/13 2/14 2/34
3/12 3/14 3/24
4/12 4/13 4/23
【数据规模和约定】
设P=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct，pi为质数。
对于100%的数据，1≤n≤109，1≤m≤5，1≤pi^ci≤10^5。
答案就是一堆组合数乘起来。。考点是组合数取模，模数长成这个样子显然要CRT合并，但每部分的组合数不能用lucas求。模数可以写成p_i^{k_i}这样的形式。于是有了扩展lucas：把C(n,m)展开变成几个阶乘的形式，然后分别处理每个阶乘就行了。假设n=19,p=3,pk=p^{2}=9.设fac[i]表示从1到i的乘积，其中不乘p的倍数的数。 $19!=1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19$
$=(1*2*4*5*7*8)*(10*11*13*14*16*17)*3^{6}*6!$
$=fac[pk]^{\lfloor \frac {n} {pk} \rfloor}*p^{\lfloor \frac {n} {p} \rfloor}*(\lfloor \frac {n} {p} \rfloor)! $
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
int n,m;
ll fac[100050];
ll w[10],sum,mods[10050],ks[10050],MOD;
ll qp(ll x,ll y,ll mod) {ll re=1;for(;y;y>>=1ll,x=x*x%mod) if(y&1ll)re=re*x%mod; return re;}
void exgcd(ll a,ll b,ll &x,ll &y,ll &p) {
if(!b) {p=a; x=1; y=0; return ;}
exgcd(b,a%b,y,x,p); y-=a/b*x;
}
ll INV(ll a,ll b) {
ll x,y,d;
exgcd(a,b,x,y,d);
return d==1?(x%b+b)%b:-1;
}
ll Fac(ll x,ll p,ll pk) {
if(!x) return 1;
return qp(fac[pk],x/pk,pk)*fac[x%pk]%pk*Fac(x/p,p,pk)%pk;
}
ll C(ll x,ll y,ll p,ll pk) {
if(x<y) return 0;
ll i,re=0;
for(i=x;i;i/=p) re+=i/p;
for(i=y;i;i/=p) re-=i/p;
for(i=x-y;i;i/=p) re-=i/p;
re=qp(p,re,pk);
if(!re) return 0;
for(fac[0]=1,i=1;i<=pk;i++) fac[i]=i%p?fac[i-1]*i%pk:fac[i-1];
return re*Fac(x,p,pk)%pk*INV(Fac(y,p,pk),pk)%pk*INV(Fac(x-y,p,pk),pk)%pk;
}
ll crt(ll x,ll y) {
ll ans=0;int i;
for(i=1;i<=mods[0];i++) {
ll Mi=MOD/ks[i],Ai=C(x,y,mods[i],ks[i]),Ti=INV(Mi,ks[i]);
ans=(ans+Mi*Ai%MOD*Ti%MOD)%MOD;
}
return ans;
}
int main() {
scanf("%lld%d%d",&MOD,&n,&m);
int i;
for(i=1;i<=m;i++) scanf("%lld",&w[i]),sum+=w[i];
if(sum>n) {
puts("Impossible"); return 0;
}
ll j=MOD;
for(i=2;1ll*i*i<=j;i++) {
if(j%i==0) {
mods[++mods[0]]=i; ks[mods[0]]=1;
while(j%i==0) j/=i,ks[mods[0]]*=i;
}
}
if(j!=1) mods[++mods[0]]=j,ks[mods[0]]=j;
ll ans=1;
for(i=1;i<=m;i++) {
ans=ans*crt(n,w[i])%MOD;
n-=w[i];
}
printf("%lld\n",ans);
}
