65 lines
1.7 KiB
C++
65 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int mod = 1e9 + 7;
|
||
const int N = 110;
|
||
int f[N];
|
||
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 C(int a, int b, int p) {
|
||
if (a < b) return 0;
|
||
int down = 1, up = 1;
|
||
|
||
for (int i = a, j = 1; j <= b; i--, j++) {
|
||
up = (LL)up * i % p;
|
||
down = (LL)down * j % p;
|
||
}
|
||
return (LL)up * qmi(down, p - 2, p) % p;
|
||
}
|
||
|
||
//卡特兰数的前几项为：1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,208012
|
||
int main() {
|
||
//目标：求出卡特兰数的前12位
|
||
|
||
//公式法计算I
|
||
//方法1:f(n)=C(n,2n)-C(n-1,2n)
|
||
for (int i = 1; i <= 12; i++)
|
||
cout << C(2 * i, i, mod) - C(2 * i, i - 1, mod) << " ";
|
||
cout << endl;
|
||
|
||
//公式法计算II
|
||
//方法2：C(n,2n)/(n+1)
|
||
for (int i = 1; i <= 12; i++)
|
||
cout << C(2 * i, i, mod) / (i + 1) << " ";
|
||
cout << endl;
|
||
|
||
//递推法计算I
|
||
//方法3：f(n)=(4n-2)/(n+1)*f(n-1)
|
||
f[0] = 1;
|
||
for (int i = 1; i <= 12; i++) {
|
||
f[i] = (LL)f[i - 1] * (4 * i - 2) / (i + 1); //注意：这里要先乘再除，否则可能丢失精度
|
||
cout << f[i] << " ";
|
||
}
|
||
cout << endl;
|
||
|
||
//递推法计算II
|
||
//方法4： f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i+1)
|
||
//要是每次都这么推，不是效率太差了吗？
|
||
memset(f, 0, sizeof f);
|
||
f[0] = 1;
|
||
for (int i = 1; i <= 12; i++) {
|
||
for (int j = 1; j <= i; j++)
|
||
f[i] += f[j - 1] * f[i - j];
|
||
cout << f[i] << " ";
|
||
}
|
||
return 0;
|
||
} |