当前位置：首页 > news >正文

数据结构与算法-数学-（同余，线性同余方程，中国剩余定理，卡特兰数，斯特林数）

news 来源：原创 2025/9/20 8:17:36

同余方程：

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;

}

同余方程：

1.1 线性同余方程 & 乘法逆元

代码：

1.2 中国剩余定理

代码：

组合数运用：

卡特兰数：

代码：

斯特林数：

第一类代码：

第二类代码：

相关文章：