书海扬帆的博客

用于求$\left( {\begin{array}{*{20}{c}}{n + m}\\m\end{array}} \right)\bmod p$, $p$为质数.

当然也要结合快速幂,不过这里是利用快速幂求逆元的啦~

代码分享


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
//Lucas定理
//结合快速幂使用
typedef long long ll;
int n,m,p,T;
ll qpow(ll x,ll m){
if(m==0) return 1;
ll tmp=qpow(x,m>>1);
tmp=(tmp*tmp)%p;
if(m%2==1) tmp=(tmp*x)%p;
return tmp;
}
ll getc(ll n,ll m){
if(m>n) return 0;
if(m>n-m) m=n-m;
ll s1=1,s2=1;
for(int i=0;i<m;i++){
s1=s1*(n-i)%p;
s2=s2*(i+1)%p;
}
return s1*qpow(s2,p-2)%p;
}
ll lucas(ll n,ll m){
if(m==0) return 1;
return getc(n%p,m%p)*lucas(n/p,m/p)%p;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&p);
printf("%d\n",lucas(n+m,m));
}
return 0;
}
</pre>



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k