bzoj2142 礼物 扩展Lucas+CRT

bzoj2142 礼物 扩展Lucas+CRT

​​ 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。 HINT

Source 考虑分析题目 他所要求的方案数其实是 Cw1n×Cw2n−w1×Cw3n−w1−w2 C n w 1 × C n − w 1 w 2 × C n − w 1 − w 2 w 3 所以把组合数打开 发现是很多阶乘形式 n!w1!×w2!×...(n−w1−w2−...)! n ! w 1 ! × w 2 ! × . . . ( n − w 1 − w 2 − . . . ) ! 那么考虑模数任意的情况需要使用扩展Lucas 即首先将模数拆分成 P=pq11×pq22... P = p 1 q 1 × p 2 q 2 . . . 这样的形式 针对每个质因数算一个模数 然后使用CRT将他们组合起来 因为模数互质所以使用普通CRT即可 普通CRT:(∑i=1totc[i]×Ppi×inv(Ppi,pi))%P ( ∑ i = 1 t o t c [ i ] × P p i × i n v ( P p i , p i ) ) % P 考虑每个组合数怎么去算 把每个阶乘和当前模数有关的项提出来 单独处理 其他和他没关的项分成三部分处理 首先就是pi p i 的幂部分 就利用公式 ans=∑i=1,i=i∗pinni a n s = ∑ i = 1 , i = i ∗ p i n n i 大概思想就是比如三次的时候算一次的时候有他二次的时候有他 三次时候有他 分三次累计 然后可以发现剩余部分变成⌊npi⌋! ⌊ n p i ⌋ ! 的结果 递归做即可 然后还有一部分 分为pqii p i q i 部分和%pqii % p i q i 模的部分暴力做即可 除的部分 算出等于npqii n p i q i 这么多次 然后对每个块内暴力算 算完用快速幂倍增即可 然后这样就算完了 最后要记得把前面幂次没有被消去的部分快速幂求一下 具体例子和方法 参见扩展Lucas求法 ​

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; }const int N=110;int prime[N],mo[N],p,n,m,tot,w[10],c[N];inline void get_frac(int md){static int tp;tp=md; for (int i=2;i*i<=tp;++i){ if (md%i) continue;prime[++tot]=i;mo[tot]=1; while(md%i==0) mo[tot]*=i,md/=i; }if (md>1) prime[++tot]=md,mo[tot]=md;}inline int ksm(ll b,int t,int md){static ll tmp; for (tmp=1;t;b=b*b%md,t>>=1) if(t&1) tmp=tmp*b%md;return tmp;}inline int jc(int n,int p,int md){ if (!n) return 1;ll tmp=1; for (int i=2;i=p?x+v-p:x+v;}int main(){ freopen("bzoj2142.in","r",stdin); p=read();n=read();m=read();ll sum=0; for (int i=1;i<=m;++i) sum+=(w[i]=read()); if (sum>n) {puts("Impossible");return 0;} get_frac(p);w[++m]=n-sum;int ans=0; for (int i=1;i<=tot;++i) c[i]=calc(prime[i],mo[i]); for (int i=1;i<=tot;++i) inc(ans,(ll)c[i]*(p/mo[i])%p*inv(p/mo[i],mo[i])%p); printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。