有T次询问,每次给出整数n,m,p,计算C(n+m,n)%p的值。输入保证p为质数。
1<=n,m,p<=1E5; 1<=T<=10
n较大,p较小且为质数时,可以用lucas定理来计算组合数:lucas(n,k,p) = lucas(n/p,k/p,p) * C(n%p,k%p,p)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)
const int Z = 100000;
int fac[Z+1], ifac[Z+1];
int power(int a, int b, int p) {
int r = 1;
for (int t = a; b; b /= 2) {
if (b & 1) r = r * t % p;
t = t * t % p;
}
return r % p;
}
int comb(int n, int k, int p) {
if (k > n) return 0;
return fac[n] * ifac[k] % p * ifac[n-k] % p;
}
int lucas(int n, int k, int p) {
if (k == 0) return 1;
return lucas(n/p, k/p, p) * comb(n%p, k%p, p) % p;
}
void solve() {
int n, m, p;
cin >> n >> m >> p;
fac[0] = 1;
rep(i,1,p-1) fac[i] = fac[i-1] * i % p;
ifac[p-1] = power(fac[p-1], p-2, p);
per(i,0,p-2) ifac[i] = ifac[i+1] * (i+1) % p;
cout << lucas(n+m, n, p) << "\n";
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1; cin >> t;
while (t--) solve();
return 0;
}
标签:return,lucas,int,定理,lgP3807,fac,ifac
From: https://www.cnblogs.com/chenfy27/p/18064733