同余方程：
1.1 线性同余方程 & 乘法逆元
线性同余方程是形如 ax≡b(mod m) 的方程，可转化为 ax+my=b 的线性不定方程，利用扩展欧几里得算法求解。当 b=1 时，x 就是 a 在模 m 意义下的乘法逆元。
代码：
#include <iostream>
using namespace std;
// 扩展欧几里得算法
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 求解线性同余方程 ax ≡ b (mod m)
bool linear_congruence(int a, int b, int m, int &x) {
int y;
int d = exgcd(a, m, x, y);
if (b % d != 0) return false;
int t = m / d;
x = (LL)x * (b / d) % m;
x = (x % t + t) % t; // 求最小正整数解
return true;
}
int main() {
int a, b, m;
cin >> a >> b >> m;
int x;
if (linear_congruence(a, b, m, x)) {
cout << x << endl;
} else {
cout << "No solution" << endl;
}
return 0;
}
1.2 中国剩余定理
中国剩余定理用于求解形如
的同余方程组，其中 m1,m2,⋯,mn 两两互质。
原理：用于求解一组两两互质的模数下的同余方程组。设m1,m2,⋯,mn是两两互质的正整数，M=m1*m2*⋯mn，Mi=M/mi，ti是Mi在模mi下的逆元，对于同余方程组x≡ai(mod mi)（i=1,2,⋯,n），其解为x=∑i=1~n ai*Mi*ti(mod M)。
这个是我们构造出来的解，一定是成立的。
算法设计思路：先计算出M和Mi，然后通过扩展欧几里得算法求出ti，最后根据公式计算出x。这样可以将多个同余方程转化为一个统一的表达式来求解。
代码：
#include <iostream>
using namespace std;
typedef long long LL;
// 扩展欧几里得算法
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 中国剩余定理
LL chinese_remainder(int n, LL *a, LL *m) {
LL M = 1, ans = 0;
for (int i = 0; i < n; i++) M *= m[i];
for (int i = 0; i < n; i++) {
LL Mi = M / m[i], x, y;
exgcd(Mi, m[i], x, y);//求解Mi * x = 1 (mod m[i])中的x
ans = (ans + a[i] * Mi * x % M) % M;
}
return (ans + M) % M;//防止负数
}
int main() {
int n;
cin >> n;
LL a[100], m[100];
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> m[i];
cout << chinese_remainder(n, a, m) << endl;
return 0;
}
组合数运用：
卡特兰数：
常用于计算如二叉树形态数、出栈序列数等问题，递推公式为
1出栈序列计数：一个栈的进栈序列为1,2,3,⋯,n，不同的出栈序列种数是卡特兰数Cn。例如，当n=3时，进栈序列为1,2,3，可能的出栈序列有123、132、213、231、321，共5种，这正是卡特兰数C3=5。
2买票找零问题：有2n个人排成一行进入剧场，入场费5元，其中n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，使得只要有10元的人买票，售票处就有5元的钞票找零的方法数是卡特兰数Cn。将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈，就与出栈序列问题等价。
3凸多边形三角划分：在一个凸n边形中，通过若干条互不相交的对角线，把这个多边形划分成若干个三角形，不同划分的方案数是卡特兰数Cn−2。例如，凸六边形的三角划分方案数为C4=14种。
4圆上点的连线问题：在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数是卡特兰数Cn。
5给定节点组成二叉搜索树：给定n个节点，能构成的不同二叉搜索树的数量是卡特兰数Cn。例如，当n=3时，可以构成5种不同的二叉搜索树。
6括号匹配问题：n对括号正确匹配的字符串数是卡特兰数Cn。例如，3对括号有5种正确配对方式：(())、()()、(()())、()(()))、((()))。
7,一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
代码：
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init() {
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;
}
}
}
int catalan(int n) {
return (LL)c[2 * n][n] * qmi(n + 1, mod - 2, mod) % mod;}
// 快速幂
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main() {
init();
int n;
cin >> n;
cout << catalan(n) << endl;
return 0;
}
求法2：
int f[N];
f[0]=1;
for(int i=1;i<=n;i++){
f[i]=f[i-1]*(4 * i -2）/(i + 1）;
}
return f[n];
斯特林数：
第一类斯特林数s(n,k)表示将n个不同元素分成k个非空循环排列的方案数；第二类斯特林数S(n,k)表示将n个不同元素分成k个非空子集的方案数。
第一类斯特林数的递推公式为s(n,k)=s(n−1,k−1)+(n−1)*s(n−1,k)
第二类斯特林数的递推公式为S(n,k)=S(n−1,k−1)+k*S(n−1,k)。
第一类代码：
#include <iostream>using namespace std;const int N = 2010, mod = 1e9 + 7;int s[N][N];
void init() {
s[0][0] = 1;
for (int i = 1; i < N; i++) {
for (int j = 1; j <= i; j++) {
s[i][j] = (s[i - 1][j - 1] + (LL)(i - 1) * s[i - 1][j] % mod) % mod;
}
}
}
int main() {
init();
int n, k;
cin >> n >> k;
cout << s[n][k] << endl;
return 0;
}
第二类代码：
#include <iostream>using namespace std;const int N = 2010, mod = 1e9 + 7;int s[N][N];
void init() {
s[0][0] = 1;
for (int i = 1; i < N; i++) {
for (int j = 1; j <= i; j++) {
s[i][j] = (s[i - 1][j - 1] + (LL)j * s[i - 1][j] % mod) % mod;
}
}
}
int main() {
init();
int n, k;
cin >> n >> k;
cout << s[n][k] << endl;
return 0;
}