求解组合数

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;


int power(int x, int k) {
	int ans = 1;
	while(k) {
		if(k & 1) ans = (ans * x) % mod;
		k >>= 1; x = (x * x) % mod;
	}
	return ans % mod;
}
int C(int n, int m) {
	int a = 1, b = 1;
	for(int i = n - m + 1; i <= n; ++i) a = (a * i) % mod;
	for(int i = 2; i <= m; ++i) b = (b * i) % mod;
	return (a * power(b, mod - 2)) % mod; 
}
int lucas(int n, int m) {
	if(m == 0) return 1;
	if(n < mod && m < mod) return C(n, m);
	return (lucas(n % mod, m % mod) * lucas(n / mod, m / mod)) % mod;
}

int main() {
	
	int T; cin >> T;
	while(T--) {
		int n, m; cin >> n >> m;
		cout << luvas(n, m) << "\n";
	}

	return 0;
}

求解组合数

原文：https://www.cnblogs.com/hzy1/p/14614780.html