信息学奥赛一本通 1656：Combination
【题目链接】
ybt 1656：Combination
【题目考点】
1. 卢卡斯定理(Lucas定理）
相关知识见：洛谷 P3807 【模板】卢卡斯定理
2. 乘法逆元
相关知识见：洛谷 P1082 [NOIP 2012 提高组] 同余方程
3. 求组合数
相关知识见：【模板：求组合数】洛谷 P1313 [NOIP 2011 提高组] 计算系数
【解题思路】
本题求C n m m o d 10007 C_n^m \bmod 10007Cnmmod10007，其中n nn与m mm最大可以达到2 ∗ 10 8 2*10^82∗108。
如果直接保存[ 1 , 2 ∗ 10 8 ] [1,2*10^8][1,2∗108]范围内的所有数的阶乘模10007的值，需要长为2 ∗ 10 8 2*10^82∗108的int类型的数组，其占用内存空间为：
2 ∗ 10 8 ∗ 4 / 1024 = 781250 K B 2*10^8*4/1024=781250KB2∗108∗4/1024=781250KB，而本题内存限制为524288 K B 524288KB524288KB，该方法会内存超限。
因此本题需要使用卢卡斯定理，缩小求组合数C n m C_n^mCnm时n nn与m mm的值。
卢卡斯定理的原理，及代码写法见：洛谷 P3807 【模板】卢卡斯定理
本题也是卢卡斯定理的模板题，与上题要求十分相近，解题代码也几乎一样，具体做法不再赘述。
【题解代码】
解法1：卢卡斯定理
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=10010,P=10007;LL t,n,m,fac[N],facInv[N];LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}voidinitFac(LL n,LL M){fac[0]=1;for(inti=1;i<=n;++i)fac[i]=fac[i-1]*i%M;facInv[n]=fastPow(fac[n],M-2,M);for(inti=n-1;i>=0;--i)facInv[i]=facInv[i+1]*(i+1)%M;}LLcomb(LL n,LL m,LL M){if(n<m)return0;returnfac[n]*facInv[n-m]%M*facInv[m]%M;}LLlucas(LL n,LL m,LL P){if(m==0)return1;returncomb(n%P,m%P,P)*lucas(n/P,m/P,P)%P;}intmain(){initFac(P-1,P);cin>>t;while(t--){cin>>n>>m;cout<<lucas(n,m,P)<<endl;}return0;}