定義
若 \(p\) 為質數，且\(a\ge b\ge1\)，則有：
\[C_{a}^{b}\equiv C_{a/p}^{b/p}\cdot C_{a (mod\,p)}^{b(mod\,p)} \]拆分a與b
按照 \(p\) 進制拆分 \(a\) 與 \(b\) ,設 \(a\) 與 \(b\) 是 \(k\) 位，不足用 \(0\) 補足，
\[\left\{\begin{aligned} a&=a_0p^{0}+a_1p^{1}+\cdots+a_{k-1}p^{k-1}+a_kp^{k}\\ b&=b_0p^{0}+b_1p^{1}+\cdots+b_{k-1}p^{k-1}+b_kp^{k} \end{aligned}\tag{1} \right. \]證明\((1+x)^{p}\equiv1+x^p\,mod\,p\)
根據二項式定理有：
\[\begin{aligned} (1+x)^p&=C_p^0x^0+C_p^1x^1+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+C_p^px^p\\ &=1+C_p^1x+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+x^p\\ \end{aligned} \]\(\because p為質數\therefore1\sim p-1均與p互質\\\therefore C_p^2,C_p^3,\cdots,C_p^{p-1}均能整除p,即C_p^2,C_p^3,\cdots,C_p^{p-1}\,mod\,p=0\)
\[(1+x)^p\equiv(1+x^p)\,mod\,p\tag{2} \]即 \((1+x)^p\) 在模 \(p\) 的意義下與 \((1+x^p)\) 同余，
根據 \((1+x)^a\) 求解 \(C_b^a\)
設 \(a=\lfloor \frac{a}{p}\rfloor p+a\%p\)，\(a'=\lfloor \frac{a}{p}\rfloor\) 有：
\[\begin{aligned} (1+x)^a&=(1+x)^{\lfloor \frac{a}{p}\rfloor p+a\%p}\\ &=(1+x)^{a'p+a\%p}\\ &=(1+x)^{a'p}(1+x)^{a\%p}\\ \because a\%p=a_0 \therefore &=(1+x)^{a'p}(1+x)^{a_0}\\ &=\underline{((1+x)^p)^{a'}}(1+x)^{a_0}\\ \because公式(2) \therefore &=\underline{(1+x^p)^{a'}(1+x)^{a_0}} \end{aligned}\tag{3} \]再設 \(a'=\lfloor \frac{a'}{p}\rfloor p+a'\%p\)，\(a''=\lfloor \frac{a'}{p}\rfloor\) 有：
\[\begin{aligned} ((1+x)^p)^{a'}&=(1+x^p)^{\lfloor \frac{a'}{p}\rfloor p+a'\%p}\\ &=(1+x^p)^{a''p+a'\%p}\\ &=(1+x^p)^{a''p}((1+x)^p)^{a'\%p}\\ \because a'\%p=a_1 \therefore &=(1+x^p)^{a''p}((1+x)^p)^{a_1}\\ &=\underline{(1+x^p)^p)^{a''}((1+x)^p)^{a_1}}\\ \because公式(2) \therefore &=\underline{(1+x^{p^2})^{a''}(1+x^p)^{a_1}} \end{aligned}\tag{4} \]同理，可得到：
\[(1+x^{p^2})^{a''}=(1+x^{p^3})^{a'''}\underline{(1+x^{p^2})^{a_2}} \]這樣經過不斷的迭代，最終得到:
\[(1+x)^a=(1+x^{p^k})^{a_k}*(1+x^{p^{k-1}})^{a_{k-1}} *\cdots*(1+x^p)^{a_1}*(1+x)^{a_0}\tag{5} \]等式兩邊運用二項式分別求 \(C_a^bx^b\) ,右邊可以看作 \(b\) 個球分到了 \(k\)個 盒子里，每個盒子里面得數量就是 \(b_i(1\le i\le k)\) 得：
\[\begin{aligned} C_a^bx^b&=C_{a_k}^{b_k}x^{p^kb_k}C_{a_{k-1}}^{b_{k-1}}\,x^{p^{k-1}\,b_{k-1}}\cdots C_{a_1}^{b_1}x^{pb_1}C_{a_0}^{b_0}x^{b_0}\\ &=(\prod_{i=0}^k{C_{a_i}^{b_i}})(x^{\sum\limits_{i=0}^{k}{p^ib_i}})\\ \because 公式(1)中b的展開式 \therefore &=(\prod_{i=0}^k{C_{a_i}^{b_i}})x^b\\ \end{aligned} \]等式兩邊同時消去 \(x^b\) ，得：
\[C_a^b\,mod\,p\equiv \prod_{i=0}^{k}{C_{a_i}^{b_i}}\tag{6} \]根據遞回的程序，也可寫成：
\[C_a^b\,mod\,p=C_{a/p}^{b/p}C_{a\%p}^{b\%p}\tag{7} \]例題：
下面以AcWing 887. 求組合數 III為例：傳送門
- 使用 \(Lucas\) 定理主要使用公式\(7\)的遞推式
- 函式
int C(int a, int b)實作\(C_a^b\)的求解，使用\(C_a^b=\frac{a*(a-1)*\cdots*(a-b+1)}{b*(b-1)*\cdots*1}\),分子用逆元即可 - 參考y總：傳送門
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int p;
int qmi(int a, int b) {
int res=1;
while(b) {
if(b&1) res=(ll)res*a%p;
a=(ll)a*a%p;
b>>=1;
}
return res;
}
int C(int a, int b) {
int res=1;
for(int i=1,j=a;i<=b;++i,--j) {
res=(ll)res*j%p;
res=(ll)res*qmi(i,p-2)%p;
}
return res;
}
int lucas(ll a, ll b) {
if(a<p&&b<p) return C(a,b);
return (ll)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
int main() {
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // ONLINE_JUDGE
scanf("%d",&n);
while(n--) {
ll a,b;
scanf("%lld%lld%lld",&a,&b,&p);
printf("%d\n",lucas(a,b));
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277635.html
標籤：其他
上一篇：面試現場,斬獲大廠offer
下一篇：modebus通訊crc校驗方法