题解 P2183 【[国家集训队]礼物】

没名字可被用

2018-01-25 23:05:35

Solution

没人在这里发这题题解啊,我来发一篇。 明显答案是$C_n^{w_1}\times C_{n-w_1}^{w_2} \times \cdots$,如果要求的礼物总数超过了买的礼物,则直接输出`Impossible`。 求解一个组合数$C_n^m$对$p_i^{k_i}$的过程可以分别求分子和分母,然后再进行运算,即,求出$n!\mod p_i^{k_i}$,$m!\mod p_i^{k_i}$,$(n-m)!\mod p_i^{k_i}$后合并。注意分子可以含有大于$k_i$个$p_i$,这样的话求出来就直接为0了,而除掉分母的时候是可能会除掉一些$p_i$的;同时分母本身也可能有含有$p_i$的约数,于是统一把$p_i$移除来,不乘进答案,接下来用分子有的$p_i$的质数减掉分母的,然后乘上去即可。不可能出现减掉后为负数的情况,因为那样意味着组合数除不尽;有可能出现减掉后仍然大于$k_i$的情况,那么这个组合数在模$p_i^{k_i}$下为$0$。 具体地,对于求$n! \mod p_i^{k_i}$可以分为几个部分求解。将每个$p_i$的倍数提出一个$p_i$来,组成$p_i^{\lfloor \frac{n}{p_i} \rfloor}$;对于剩余的部分,容易发现除掉了$p_i$的数(原来是$p_i$的倍数)组成了一个新的阶乘,即$\lfloor \frac{n}{p_i} \rfloor !$,这个我们可以递归求解。剩下的数形如$1,2,\cdots,p-1,p+1,p+2,\cdots,2p-1 \cdots$(因为$p_i$的倍数已经通过前两步瓜分到阶乘和次幂里去了),由于$a \times b \mod p=(a \mod p) \times (b \mod p)$,易得$\prod _{i=1}^{p_i^{k_i}-1}i[i \mod p \neq 0]$与$\prod _{i=p_i^{k_i}+1}^{2p_i^{k_i}-1}i[i \mod p \neq 0] $在$\mod p_i^{k_i}$下是相等的,那么只需求一个$p^k$的长度的乘积在模$p_i^{k_i}$下的结果即可,而这个阶乘里包含了$ \lfloor \frac{n}{p_i^{k_i}} \rfloor$个这个余数,快速幂即可;还有剩下来的、没有达到$p_i^{k_i}$的一段数,由于长度不会超过$p_i^{k_i}$(即$10^5$),直接计算即可。 考虑求解答案,因为模的是一个和数,所以不能直接用普通的$lucas$求解。将和数$P$分解,得到$P=\prod_{i=1}^{k}p_i^{k_i}$,我们要求的答案模$p_i^{k_i}$的结果,对于单独求组合数在模每个$p_i^{k_i}$的剩余系下的结果要相同。于是考虑对于每个组合数,单独求出对$p_i^{k_i}$的结果,然后通过中国剩余定理求解即可。 代码 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=6; const int maxp=(int)1e5+5; int P,n,m,w[maxn],pri[maxp],cnt[maxp],tot=0,c[maxp],R[maxp],M[maxp]; map<int ,int > re; inline int maybs(int x) {return x<0?-x:x;} void div(int x) { for(int i=2;i*i<=x;i++) { if(x%i==0) { pri[++tot]=i;re[i]=tot; while(x%i==0) x/=i,cnt[tot]++; } } if(x!=1) { if(re.find(x)==re.end()) pri[++tot]=x,re[x]=tot; cnt[re[x]]++; } } int quickpow(int x,int k) { int ret=1; while(k>0) { if(k&1) ret=ret*x; x=x*x; k>>=1; } return ret; } int quickpow(int x,int k,int mo) { int ret=1; while(k>0) { if(k&1) ret=1ll*ret*x%mo; x=1ll*x*x%mo; k>>=1; } return ret; } int gcd(int a,int b) {return b==0?a:gcd(b,a%b);} int extgcd(int a,int b,int &x,int &y) { if(b==0) {x=1,y=0; return a;} else {int d=extgcd(b,a%b,y,x);y-=a/b*x;return d;} } int inv(int q,int p) { assert(gcd(p,q)==1); int x,y; extgcd(q,p,x,y); x=(x%p+p)%p; if(!x) x+=p; return x; } int Cnt(int x,int p) { if(x==0) return 0; return Cnt(x/p,p)+x/p; } typedef pair<int ,int > pii; #define fir first #define sec second #define MP make_pair pii Cal(int x,int p,int k) { if(x==1 || x==0) return MP(1,0); int ret=1,del=0,tmp=quickpow(p,k); int cou=Cnt(x,p); del=cou; pii nw=Cal(x/p,p,k); ret=1ll*ret*nw.fir%tmp; if(x>=tmp) { int lev=1; for(int i=1;i<tmp;i++) { if(i%p==0) continue; lev=1ll*lev*i%tmp; } ret=1ll*ret*quickpow(lev,x/tmp,tmp)%tmp; } for(int i=x;i>=1;i--) { if(i%tmp==0) break; if(i%p==0) continue; ret=1ll*ret*i%tmp; } return MP(ret,del); } int getAns() { for(int i=1;i<=tot;i++) M[i]=1; for(int i=1;i<=tot;i++) { for(int j=1;j<=tot;j++) if(i==j) continue; else M[i]=1ll*M[i]*R[j]%P; } int ret=0; for(int i=1;i<=tot;i++) ret=(ret+((1ll*c[i]*M[i]%P)*1ll*inv(M[i],R[i]))%P)%P; return ret; } int main() { scanf("%d",&P); div(P); scanf("%d%d",&n,&m); int sum=0; for(int i=1;i<=m;i++) {scanf("%d",&w[i]);sum+=w[i];} if(sum>n) {printf("Impossible\n");exit(0);} int ans=1,N=n,M,res=1; pii up,dw1,dw2; for(int i=1;i<=m;i++) { M=w[i]; for(int j=1;j<=tot;j++) R[j]=quickpow(pri[j],cnt[j]); for(int j=1;j<=tot;j++) { ans=1; up=Cal(N,pri[j],cnt[j]); dw1=Cal(M,pri[j],cnt[j]),dw2=Cal(N-M,pri[j],cnt[j]); up.sec-=dw1.sec; up.sec-=dw2.sec; assert(up.sec>=0); if(up.sec>=cnt[j]) ans=0; else { ans=1ll*ans*up.fir%R[j]; ans=1ll*ans*inv(dw1.fir,R[j])%R[j]; ans=1ll*ans*inv(dw2.fir,R[j])%R[j]; ans=1ll*ans*quickpow(pri[j],up.sec,R[j])%R[j]; } c[j]=ans; } res=1ll*res*getAns()%P; N-=w[i]; } printf("%d\n",res); return 0; } ```