組合

給出組合數(shù)C(n,m), 表示從n個(gè)元素中選出m個(gè)元素的方案數(shù)。例如C(5,2) = 10, C(4,2) = 6.可是當(dāng)n,m比較大的時(shí)候，C(n,m)很大！于是xiaobo希望你輸出 C(n,m) mod p的值！

Input

輸入數(shù)據(jù)第一行是一個(gè)正整數(shù)T,表示數(shù)據(jù)組數(shù) (T <= 100) 接下來(lái)是T組數(shù)據(jù)，每組數(shù)據(jù)有3個(gè)正整數(shù) n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素?cái)?shù))

Output

對(duì)于每組數(shù)據(jù)，輸出一個(gè)正整數(shù)，表示C(n,m) mod p的結(jié)果。

Sample Input

2 5 2 3 5 2 61

Sample Output

1 10 //盧卡斯定理求組合數(shù) #include<cstdio> #include<cstring> using namespace std; typedef long long ll; //快速冪 ll fastPow(ll a,ll b,ll p) {ll ret=1;while(b){if(b&1)ret=(ret*a)%p;a=(a*a)%p;b>>=1;}return ret; } //費(fèi)馬小定理求逆元fastPow(a,b-2,b) ll c(ll n,ll m,ll p) {if(m==0) return 1;//if(m>n-m) m=n-m;ll up=1,down=1;for(int i=1;i<=m;i++){up=(up*(n-i+1))%p;down=(down*i)%p;}return up*fastPow(down,p-2,p)%p; } //求C(n,m)%p ll lucas(ll n,ll m,ll p) {if(m==0) return 1;return c(n%p,m%p,p)*lucas(n/p,m/p,p)%p; } int main() {int T;ll n,m,p;scanf("%d",&T);while(T--){scanf("%I64d%I64d%I64d",&n,&m,&p);//scanf("%lld%lld%lld",&n,&m,&p);//錯(cuò)誤//getFact(p);printf("%I64d\n",lucas(n,m,p));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的FZU2020 lucas定理求解组合数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。