经典算法 求C(N, K) % mod，保证mod是质数

求C(N, K) % mod，保证mod是质数

问题描述

给你三个整数N,K,mod保证mod是一个质数，求组合数C(N, K) % mod。

输入描述

输入有多组，输入第一行为两个整数T，mod。接下来2 - T + 1行，每行输入N， K。

输出描述

每一组输入，输出C(N, K) % mod。

输入示例

9 1000003
6 4
7 5
3 2
10 5
100 50
1000 500
10000 5000
100000 50000
1000000 500000

输出示例

15
21
3
252
440004
175726
737315
781911
375001

c++代码(乘法逆元)

这种方法大致可以处理N,K<= 1000000,mod <= 1000000009。

保证mod为质数，用费马小定理求逆元。

#include<bits/stdc++.h>using namespace std;typedef __int128_t ll;//防止数据溢出long long T, N, K, mod;//保证mod是质数
vector<ll> jiecen;ll fastPow(ll a, ll b, ll mod) {//返回a^b % modif (b == 0) return 1 % mod;if (b == 1) return a % mod;ll k = fastPow(a, b / 2, mod);if (b % 2 == 0) return (k * k) % mod;else return (((k * k) % mod) * a) % mod;
}ll mod_inverse(ll A, ll mod) { return fastPow(A, mod - 2, mod); }//求A % mod 的逆元ll cnk(ll N, ll K, ll mod) { return (jiecen[N] * mod_inverse((jiecen[K] * jiecen[N - K]) % mod, mod)) % mod; }//返回组合数C(N, K) % modint main() {cin >> T >> mod;jiecen = vector<ll>(1000001, 1);//预处理阶乘for (int i = 1; i <= 1000000; i++) jiecen[i] = (jiecen[i - 1] * i) % mod;while(T--) {cin >> N >> K;cout << (long long)cnk(N, K, mod) << endl;}return 0;
}//by wqs

c++代码(卢卡斯定理)

大致可以处理N，K <= 1 * 10^18, mod <= 1000000。

卢卡斯递归过程中可能会出现N < K,这个时候cnk函数要返回0

#include<bits/stdc++.h>using namespace std;typedef __int128_t ll;vector<ll> jiecen;
long long T, N, K, mod;ll fastPow(ll a, ll b, ll mod) {//返回a^b % modif (b == 0) return 1 % mod;if (b == 1) return a % mod;ll k = fastPow(a, b / 2, mod);if (b % 2 == 0) return (k * k) % mod;else return (((k * k) % mod) * a) % mod;
}ll mod_inverse(ll A, ll mod) { return fastPow(A, mod - 2, mod); }//求A % mod 的逆元ll cnk(ll N, ll K, ll mod) { return N >= K ? (jiecen[N] * mod_inverse((jiecen[K] * jiecen[N - K]) % mod, mod)) % mod : 0; }//返回组合数C(N, K) % modll Lucas(ll N, ll K, ll mod) { return K == 0 ? 1 : (cnk(N % mod, K % mod, mod) * Lucas(N / mod, K / mod, mod)) % mod; }int main() {cin >> T >> mod;jiecen = vector<ll>(mod, 1);for (int i = 1; i <= mod - 1; i++) jiecen[i] = (__int128_t(jiecen[i - 1]) * i) % mod;while(T--) {cin >> N >> K;cout << (long long)Lucas(N, K, mod) << endl;}return 0;
}//by wqs