1.递推
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define int long long //可能会超时
#define PII pair<int,int>
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2005;
int a, b,n;
int c[N][N];
signed main()
{ios::sync_with_stdio, cin.tie(0), cout.tie(0);for (int i = 0;i <N;i++) {for (int j = 0;j <= i;j++) {if (!j) c[i][j] = 1;else c[i][j] = (c[i-1][j] + c[i-1][j - 1])%mod;}}cin >> n;while (n--) {cin >> a >> b;cout << c[a][b] << endl;}return 0;
}
2.定义出发,快速幂逆元
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define int long long //可能会超时
#define PII pair<int,int>
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e5 + 5;
int fact[N], infact[N];
int n;
int pow(int a, int b, int p) {int ans = 1;while (b) {if (b & 1) ans = ans * a % p;b >>= 1;a = a * a % p;}return ans;
}
signed main()
{ios::sync_with_stdio, cin.tie(0), cout.tie(0);fact[0] = infact[0] = 1;for (int i = 1;i < N;i++) {fact[i] = fact[i - 1] * i % mod;infact[i] = infact[i - 1] * pow(i, mod - 2, mod) % mod;}cin >> n;while (n--) {int a, b;cin >> a >> b;cout << fact[a] * infact[b] % mod * infact[a - b] % mod;puts("");}return 0;
}
3.卢卡斯定理
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define int long long //可能会超时
#define PII pair<int,int>
const int INF = 0x3f3f3f3f, mod = 998244353;
int a, b, p;
int n;
int pow(int a, int b, int p) {int ans = 1;while (b) {if (b & 1) ans = ans * a % p;a = a * a % p;b >>= 1;}return ans;
}
int C(int a, int b, int p) {if (b > a) return 0;int ans = 1;for (int i = 1,j = a;i <= b;i++, j--) {ans = ans * j % p;ans = ans * pow(i, p - 2, p) % p;}return ans;
}
int lucas(int a, int b, int p) {if (a < p && b < p) return C(a, b, p);return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
signed main()
{ios::sync_with_stdio, cin.tie(0), cout.tie(0);cin >> n;while (n--) {cin >> a >> b >> p;cout << lucas(a, b, p) << endl;}return 0;
}
4.无模数,高精度
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5010;
int primes[N], cnt;
int sum[N];
bool st[N];
void get_primes(int n)
{for (int i = 2; i <= n; i++){if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}
int get(int n, int p)
{int res = 0;while (n){res += n / p;n /= p;}return res;
}
vector<int> mul(vector<int> a, int b)
{vector<int> c;int t = 0;for (int i = 0; i < a.size(); i++){t += a[i] * b;c.push_back(t % 10);t /= 10;}while (t){c.push_back(t % 10);t /= 10;}return c;
}
int main()
{int a, b;cin >> a >> b;get_primes(a);for (int i = 0; i < cnt; i++){int p = primes[i];sum[i] = get(a, p) - get(a - b, p) - get(b, p);}vector<int> res;res.push_back(1);for (int i = 0; i < cnt; i++)for (int j = 0; j < sum[i]; j++)res = mul(res, primes[i]);for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);puts("");return 0;
}