这是一道 CTSC 水题
题目描述
一年一度的圣诞节快要来到了. 每年的圣诞节小 E 都会收到许多礼物, 当然他也会送出许多礼物. 不同的人物在小 E 心目中的重要性不同, 在小 E 心中分量越重的人, 收到的礼物会越多. 小 E 从商店中购买了 n 件礼物, 打算送给 m 个人, 其中送给第 i 个人礼物数量为 wi. 请你帮忙计算出送礼物的方案数 (两个方案被认为是不同的, 当且仅当存在某个人在这两种方案中收到的礼物不同). 由于方案数可能会很大, 你只需要输出模 P 后的结果.
输入输出格式
输入格式:
输入的第一行包含一个正整数 P, 表示模;
第二行包含两个整整数 n 和 m, 分别表示小 E 从商店购买的礼物数和接受礼物的人数;
以下 m 行每行仅包含一个正整数 wi, 表示小 E 要送给第 i 个人的礼物数量.
输出格式:
若不存在可行方案, 则输出 "Impossible", 否则输出一个整数, 表示模 P 后的方案数.
输入输出样例
输入样例 #1: 复制 100 4 2 1 2
输出样例 #1: 复制
12
输入样例 #2: 复制 100 2 2 1 2
输出样例 #2: 复制 Impossible
说明
[样例说明]
下面是对样例 1 的说明.
以 "/" 分割,"/" 前后分别表示送给第一个人和第二个人的礼物编号. 12 种方案详情如下:
- /23 1/24 1/34
- /13 2/14 2/34
- /12 3/14 3/24
- /12 4/13 4/23
设 P=p1^c1 * p2^c2 * p3^c3 * ... *pt ^ ct,pi 为质数.
对于 15% 的数据, n≤15,m≤5,pi^ci≤10^5;
在剩下的 85% 数据中, 约有 60% 的数据满足 t≤2,ci=1,pi≤10^5, 约有 30% 的数据满足 pi≤200.
对于 100% 的数据, 1≤n≤10^9,1≤m≤5,1≤pi^ci≤10^5,1≤P≤10^9.
这个思路真的是很水很水很水
思路学过组合数的都能想出来, 这道题主要就是要会 exlucas, 可以看我的博客点这里
唯一注意的就是不要手残, 不写函数名, 用一个括号括上几个变量, 因为这样不会 CE 但是得调试半天 (我真是瞎了 QAQ)
上代码!
- #include<cstdio>
- #include<algorithm>
- #define lt long long
- #define rt register lt
- #define il inline
- using namespace std;
- lt p,n,m,w,tot,ans=1;
- namespace misaki
- {
- il lt gcd(lt a,lt b){return b?gcd(b,a%b):a;}
- il lt lcm(lt a,lt b){return a/gcd(a,b)*b;}
- il lt ksc(lt a,lt b,lt mod)
- {
- if(a==0||b==0)return 0;
- lt fina=0,kk=1;
- if(a<0)a=-a,kk=-kk;
- if(b<0)b=-b,kk=-kk;
- while(b)
- {
- if(b%2)fina=(fina+a)%mod;
- b>>=1,a=(a+a)%mod;
- }
- return fina%mod*kk;
- }
- il lt ksm(lt a,lt k,lt mod)
- {
- if(!k)return 1;
- lt fina=1;
- while(k)
- {
- if(k%2)fina=ksc(fina,a,mod);
- k>>=1,a=(a*a)%mod;
- }
- return fina%mod;
- }
- il void ex_gcd(lt a,lt b,lt &x,lt &y)
- {
- if(!b)x=1,y=0;
- else
- {
- ex_gcd(b,a%b,x,y);
- lt tt=x;x=y,y=tt-a/b*x;
- }
- }
- il lt exgcd(lt a,lt b,lt c)
- {
- lt gc=gcd(a,b),x=0,y=0;
- if(c%gc){ printf("aaa");return -1;}
- a/gc,b/=gc,c/=gc;
- ex_gcd(a,b,x,y);
- return (x*c%b+b)%b;
- }
- il lt inv(lt a,lt p)
- {
- if(!a)return 0;
- return exgcd(a,p,1);
- }
- }
- namespace lucas
- {
- using namespace misaki;
- il lt fac(const lt n,const lt pi,const lt pk)//n!%p^k
- {
- if(n==1||n==0)return 1;
- lt ans=1;
- for(rt i=2;i<pk;i++)
- if(i%pi)ans=ans*i%pk;
- ans=ksm(ans,n/pk,pk);
- for(rt i=2;i<=n%pk;i++)
- if(i%pi)ans=ans*i%pk;
- return ksc(ans,fac(n/pi,pi,pk),pk);
- }
- il lt C(const lt n,const lt m,const lt pi,const lt pk)//C(n,m)%p^k
- {
- lt up=fac(n,pi,pk),dl=fac(m,pi,pk),dr=fac(n-m,pi,pk),sum=0;
- for(rt i=n;i;i/=pi)sum+=i/pi;
- for(rt i=m;i;i/=pi)sum-=i/pi;
- for(rt i=n-m;i;i/=pi)sum-=i/pi;
- return up*inv(dl,pk)%pk*inv(dr,pk)%pk*ksm(pi,sum,pk)%pk;
- }
- il lt exlucas(const lt n,const lt m,const lt P)
- {
- lt tt=P,ans=0;
- for(rt i=2;i<=tt;i++)
- if(tt%i==0)
- {
- lt pi=i,pk=1;
- while(!(tt%i))tt/=i,pk*=i;
- ans=(ans+C(n,m,pi,pk)*(P/pk)%P*inv(P/pk,pk)%P)%P;
- }
- return ans%P;
- }
- }
- int main()
- {
- scanf("%lld%lld%lld",&p,&n,&m);bool fl=0;
- for(rt i=1;i<=m;i++)
- {
- scanf("%lld",&w);
- if(n<w){fl=1;break;}tot+=w,ans=(ans*lucas::exlucas(n,w,p))%p,n-=w;
- }
- if(fl)puts("Impossible");
- else printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2880937.html