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

题不是很难，黑题应该~~虚高~~了 看到题之后，应该就能写出式子 $$ans=\prod_{i=1}^{m}C_{n-\sum_{j=1}^{i-1}w_j}^{w_i}(mod\ P)$$ 式子看起来很麻烦，其实很好想 当我们给第一个人送礼物的时候，我们有$n$个礼物，要选$w_1$个，方案就有$C_n^{w_{1}}$种 然后给第二个人送礼物的时候，我们剩下$n-w_1$个礼物，要选$w_2$个，方案有$C_{n-w_1}^{w_2}$种 就这样一直送到第$m$个人，而根据乘法原理，就得到这个式子了 这道题似乎就做完了，但在算$C_n^m(mod\ p_i^{c_i})$时又遇到了瓶颈：$p_i^{c_i}$不是质数 既然不是质数，我们就不能用$Lucas$定理来求，这就需要用到$ExLucas$了 虽然是扩展的，但和$Lucas$完全沾不上边 我们观察到题目给了$P=\prod _{i=1}^{t}p_{i}^{c_i}$ 而$p_i$是质数，那么所有的$p_i^{c_i}$都是互质的 那么我们只要对于每个$p_i^{k=c_i}$求出其$C_n^m\ mod\ p_i^k$的值，然后用**中国剩余定理**就可以算出最小正整数解 问题转化成了如何快速的求$C_n^m\ mod\ p^k$ 把组合数展开，我们得到 $$\frac{n!}{m!(n-m)!}\ mod\ p^k$$ 那么只要快速求出模意义下的阶乘就好了 如果我们要求$x!\ mod\ p^k$，假设$x=17,p=2,k=3$，观察一下式子 $$17!=1\times2\times3\times4\times5\times6\times7\times8\times9\times10\times11\times12\times13\times14\times15\times16\times17$$ 化式子$17!=$ $$2\times4\times6\times8\times10\times12\times14\times16\times1\times3\times5\times7\times9\times11\times13\times15\times17$$ $$(2\times1)\times(2\times2)\times(2\times3)\times…\times(2\times8)\times(1\times3\times5\times…\times17)$$ $$2^8\times(1\times2\times3\times…\times8)\times(1\times3\times5\times…\times17)$$ $$2^8\times8!\times(1\times3\times5\times7\times9\times11\times13\times15\times17)$$ 而在模$p^k=2^3=8$意义下$1\times3\times5\times7=9\times11\times13\times15$ 所以式子就变成了 $$2^8\times8!\times(1\times3\times5\times7)^2\times17$$ 那么$x!$就变成了$p^n\times t!\times(a_1\times a_2\times…a_m)^r\times a_{m+1}\times…a_{q}$ 可以看出$n=t=\left \lfloor \frac{x}{p} \right \rfloor,r=\left \lfloor \frac{x}{p^k} \right \rfloor$，其中$t!$可以一直递归求解，然后后面的暴力算 这样这个题就做完啦QAQ **Code** ``` cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #define int long long using namespace std; int p[200000],n,m,P,cnt,z[200000],a[200000],ans; void exgcd(int a,int b,int &x,int &y) //扩欧 { if (!b)x=1,y=0; else { exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; } } int mypow(int a,int x,int p) //快速幂 { int s=1; while (x) { if (x&1)s=s*a%p; a=a*a%p; x>>=1; } return s; } int fac(int n,int a,int b) //求阶乘 { if (!n)return 1; int s=1; for (int i=1;i<=b;i++) //处理a1*a2*…am if (i%a!=0) s=s*i%b; s=mypow(s,n/b,b); for (int i=1;i<=n%b;i++) //处理am+1*…aq if (i%a!=0) s=s*i%b; return s*fac(n/a,a,b)%b; //递归求解 } int inv(int a,int b) //求逆元 { int x,y; exgcd(a,b,x,y); return (x%b+b)%b; } int C(int m,int n,int a,int b) //处理组合数 { int nn=fac(n,a,b),mm=fac(m,a,b),nm=fac(n-m,a,b),po=0; //求阶乘 for (int i=n;i;i/=a) //处理n^p中的p po+=i/a; for (int i=m;i;i/=a) po-=i/a; for (int i=n-m;i;i/=a) po-=i/a; return nn*mypow(a,po,b)%b*inv(mm,b)%b*inv(nm,b)%b; } signed main() { cin>>n>>m>>P; int pp=P; for (int i=2;i*i<=P;i++) //分解 if (pp%i==0) { int x=i; z[++cnt]=i; while (pp%x==0)x*=i; x/=i; p[cnt]=x; pp/=x; } if (pp!=1)p[++cnt]=pp,z[cnt]=pp; for (int i=1;i<=cnt;i++) a[i]=C(m,n,z[i],p[i]); for (int i=1;i<=cnt;i++) //中国剩余定理 { int pi=P/p[i],x,y; exgcd(pi,p[i],x,y); ans=((ans+pi*a[i]*x%P)+P)%P; } cout<<ans<<endl; return 0; } ```