2142: 礼物

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 701  Solved: 283
[Submit][Status][Discuss]

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。

组合数取模终极题目。
这道题的答案很好算C(n,tot)+C(tot,w[1])+C(tot-w[1],w[2])+...
由于n很大，想到用lucas定理，但是模不是质数！！
首先质数的幂之间一定互质，那么我们可以把模分解成几个质数的幂的乘积的形式，对每一个质数的幂求解，然后用中国剩余定理将他们合并起来即可。
那么如何快速计算组合数对质数的幂取模呢？
C(n,m)=n!/(m!*(n-m)!)
我们可以把分子分母分别化成t1*p^u1，t2*p^u2的形式，然后把C(n,m)=t1/t2 *p^(u1-u2)，此时t1/t2可以用扩展欧几里得直接求出，乘上p^(u1-u2)就是答案。
可是如何快速求出n!=t*p^u的t和u的值呢？
我们把所有是p的倍数的数提出来，先不考虑。
先考虑t的值（注意所有是p的倍数的数不参与计算）： 如果y=n/(p^u)，如果y>1那么我们可以算出1-p^u的值为ans,那么t=ans^y*剩下数的乘积，否则直接暴力算1-n
再看u的值，p的倍数的数有1*p,2*p,3*p.....k*p（k=n/p）,我们把p提出来之后就变成了1,2,3...k，于是问题变成了更小规模的原问题！递归解决即可~ 复杂度是线性的~
#include #include #include #include #include #include #define N 100000+5 #define LL long long #define pa pair #define mp make_pair #define fi first #define se second using namespace std; LL mod,a[N]; int n,m,v[N],p[N],s[100],tot,num; struct divi { int p,c,pc; }w[N]; void Prepare() { int cnt=0; for (int i=2;i<=100000;i++) if (!v[i]) { p[++cnt]=i; for (int j=i;j<=100000;j+=i) v[j]=1; } num=0; LL x=mod; for (int i=1;i<=cnt;i++) { if (x<=1) break; if (x%p[i]) continue; w[++num].p=p[i]; w[num].pc=1; while (x%p[i]==0) w[num].c++,x/=p[i],w[num].pc*=p[i]; } } LL Pow(LL a,int n,LL mod) { LL base=a,ans=1; while (n) { if (n&1) ans=ans*base%mod; base=base*base%mod; n>>=1; } return ans; } void Exgcd(LL a,LL b,LL &d,LL &x,LL &y) { if (!b) { d=a,x=1,y=0; return; } Exgcd(b,a%b,d,y,x); y-=x*(a/b); } LL Inv(LL a,LL n) { LL xx,yy,d; Exgcd(a,n,d,xx,yy); return (xx%n+n)%n; } pa Fac(int k,LL n) { if (n==0) return mp(0,1); int x=n/w[k].p,y=n/w[k].pc; LL ans=1; if (y) { for (int i=2;in) { puts("Impossible"); return 0; } ans=C(n,tot)%mod; for (int i=1;i<=m;i++) { ans=ans*C(tot,s[i])%mod; tot-=s[i]; } printf("%lld ",ans); return 0; }