目录
拓展的场景分析
1.圆上连接线段
2.二叉树问题
3.多边形划分三角形问题
补充的例题
P1976 鸡蛋饼
P1722 矩阵 II
通过取模处理判断选择用哪个式子编辑
P2532 [AHOI2012] 树屋阶梯
P3978 [TJOI2015] 概率论
拓展的场景分析
1.圆上连接线段
一个圆上有2*n个点，两两连接且不相交的方法数有多少？
我们首先给圆上的点标记为1,2……2*n；
然后我们会发现当奇数点和奇数点存在连接，或者偶数点和偶数点存在连接，那么一定会有相交的线段，因此我们知道如果要让其没有相交的线段，就只能奇数点与偶数点进行配对，因此我们可以将奇数点作为左括号，偶数点作为右括号，这不就是卡特兰数的板子吗？
2.二叉树问题
给定n个点，判断可以产生多少个不同种类的二叉树
我们用f [ i ] 表示i个点能够产生多少的二叉树
我们可以先固定一个点作为二叉树的根，
假设左子树的结点有0个，右子树的节点有n-1个，因此此时的二叉树的数量为f[0]*f[n-1]
假设左子树的节点有1个，右子树的节点有n-2个，因此此时二叉树的数量为f[1]*f[n-2]
……
假设左子树的节点有n-1个，右子树的节点有0个，因此此时二叉树的数量为f[n-1]*f[0]
这样的形式应该就想到了卡特兰数的递推式了吧，因此也是卡特兰数的一个应用场景
3.多边形划分三角形问题
一个有n+2条边的一个多边形，完全划分成三角形且连线不相交，问你有多少种方法数
这个问题有点儿像第二个问题的一个变形
我们以这个n为6的正八边形来举例，我们首先要固定底边为1,8
首先我们链接2,1,8三个点作为固定的三角形，固定左边的三角形有0边形，其实就是f[0]，右边有个7边型其实就是f[5]，因此此时的方法数为f[0]*f[5]
当我们去将3,1,8作为固定三角形
我们会发现左边是个三角形，也就是f[1]，右边是个六边形也就是f[4]
此时方法数为f[1]*f[4]
依次递推后，我们发现其实这还是个卡特兰数，还是用的那个递推式的形式
补充的例题
P1976 鸡蛋饼
这题不就是对应上面那个模版吗，圆上的n个点，这不就是卡特兰数，直接用我们伟大的通项式即可，先用阶乘表去求出2*n以内的阶乘 ，然后用逆元阶乘表去求出2*n以内的阶乘的逆元，然后再去求（n+1）的逆元，然后用公式C(2*n,n)/(n+1)即可求出最终结果，如果用通项式的变式也可以求出来，这里我就不说了，都是一个道理，都需要用到这两张表
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int mod=1e8+7;
int f[100005];
int inv[100005];
int fast(int a, int b)
{long long result = 1;long long base = a;while (b > 0) {if (b % 2 == 1) {result = (result * base)%mod ;}base = (base * base)%mod ;b /= 2;}return result%mod;
}
int c(int n,int k)
{return f[n]*inv[n-k]%mod*inv[k]%mod;
}
signed main()
{cin>>n;f[0]=1;for(int i=1;i<=2*n;i++){f[i]=(f[i-1]*i)%mod;}inv[2*n]=fast(f[2*n],mod-2);for(int i=2*n-1;i>=0;i--){inv[i]=(inv[i+1]*(i+1))%mod;}cout<<(c(2*n,n)-c(2*n,n-1)+mod)%mod;
}P1722 矩阵 II
这题先看数据，就100个，那么很明显，上一篇的四个方法的时间复杂度都不会超，但是一看取模100，那这个是个偶数，并不是质数，逆元用不了了，只能用递推式去求，然后每次去取模100，最终求出结果即可
#include<bits/stdc++.h>
using namespace std;
#define int long longint n;
int f[105];
int mod=100;
signed main()
{cin>>n;f[0]=f[1]=1;for(int i=2;i<=n;i++){for(int j=0;j<i;j++){f[i]=(f[j]*f[i-1-j]+f[i])%mod;}}cout<<f[n];return 0;
} 通过取模处理判断选择用哪个式子
这个是来自于左神的取模处理说明，可供大家参考
四大公式，来自于上篇博客
P2532 [AHOI2012] 树屋阶梯
这题怎么说呢？也是那个递推式的形式，我在下面给大家画个图，大家可能就明白了
假设我们对于n为5来进行分析，我们阶梯的轮廓肯定为，我们有五个转折角
假设我们覆盖了1这个转折角，那么上边的矩形覆盖为0，右边的矩形覆盖高度为4，就是f[0]*f[4]
但是如果是覆盖了2这个转角，则上面剩下1，下面剩下3，也就是f[1]*f[3]还是那个递推式
因此还是卡特兰数，但是没有取模只能用高精度+卡特兰数，但是我有凯哥给的高精度板子，直接秒了，没什么可说的——分享高精度板子链接
#include<bits/stdc++.h>
using namespace std;
const int base = 1000000000;
const int base_digits = 9;
struct Bint {vector<int> a;int sign;Bint() :sign(1) {}Bint(long long v) {*this = v;}Bint(const string &s) {read(s);}void operator=(const Bint &v) {sign = v.sign;a = v.a;}void operator=(long long v) {sign = 1;if (v < 0)sign = -1, v = -v;for (; v > 0; v = v / base)a.push_back(v % base);}Bint operator+(const Bint &v) const //Addition Operation{if (sign == v.sign) {Bint res = v;for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {if (i == (int) res.a.size())res.a.push_back(0);res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);carry = res.a[i] >= base;if (carry)res.a[i] -= base;}return res;}return *this - (-v);}Bint operator-(const Bint &v) const //Subtraction Function{if (sign == v.sign) {if (abs() >= v.abs()) {Bint res = *this;for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);carry = res.a[i] < 0;if (carry)res.a[i] += base;}res.trim();return res;}return -(v - *this);}return *this + (-v);}void operator*=(int v) //Multiplication Function{if (v < 0)sign = -sign, v = -v;for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {if (i == (int) a.size())a.push_back(0);long long cur = a[i] * (long long) v + carry;carry = (int) (cur / base);a[i] = (int) (cur % base);//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));}trim();}Bint operator*(int v) const {Bint res = *this;res *= v;return res;}friend pair<Bint, Bint> divmod(const Bint &a1, const Bint &b1) {int norm = base / (b1.a.back() + 1);Bint a = a1.abs() * norm;Bint b = b1.abs() * norm;Bint q, r;q.a.resize(a.a.size());for (int i = a.a.size() - 1; i >= 0; i--) {r *= base;r += a.a[i];int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];int d = ((long long) base * s1 + s2) / b.a.back();r -= b * d;while (r < 0)r += b, --d;q.a[i] = d;}q.sign = a1.sign * b1.sign;r.sign = a1.sign;q.trim();r.trim();return make_pair(q, r / norm);}Bint operator/(const Bint &v) const //Division Function{return divmod(*this, v).first;}Bint operator%(const Bint &v) const //Modulus Operation{return divmod(*this, v).second;}void operator/=(int v) //Shorthand Operation{if (v < 0)sign = -sign, v = -v;for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {long long cur = a[i] + rem * (long long) base;a[i] = (int) (cur / v);rem = (int) (cur % v);}trim();}Bint operator/(int v) const {Bint res = *this;res /= v;return res;}int operator%(int v) const {if (v < 0)v = -v;int m = 0;for (int i = a.size() - 1; i >= 0; --i)m = (a[i] + m * (long long) base) % v;return m * sign;}void operator+=(const Bint &v) {*this = *this + v;}void operator-=(const Bint &v) {*this = *this - v;}void operator*=(const Bint &v) {*this = *this * v;}void operator/=(const Bint &v) {*this = *this / v;}bool operator<(const Bint &v) const {if (sign != v.sign)return sign < v.sign;if (a.size() != v.a.size())return a.size() * sign < v.a.size() * v.sign;for (int i = a.size() - 1; i >= 0; i--)if (a[i] != v.a[i])return a[i] * sign < v.a[i] * sign;return false;}bool operator>(const Bint &v) const {return v < *this;}bool operator<=(const Bint &v) const {return !(v < *this);}bool operator>=(const Bint &v) const {return !(*this < v);}bool operator==(const Bint &v) const {return !(*this < v) && !(v < *this);}bool operator!=(const Bint &v) const {return *this < v || v < *this;}void trim() {while (!a.empty() && !a.back())a.pop_back();if (a.empty())sign = 1;}bool isZero() const {return a.empty() || (a.size() == 1 && !a[0]);}Bint operator-() const {Bint res = *this;res.sign = -sign;return res;}Bint abs() const {Bint res = *this;res.sign *= res.sign;return res;}long long longValue() const {long long res = 0;for (int i = a.size() - 1; i >= 0; i--)res = res * base + a[i];return res * sign;}friend Bint gcd(const Bint &a, const Bint &b) //GCD Function(Euler Algorithm){return b.isZero() ? a : gcd(b, a % b);}friend Bint lcm(const Bint &a, const Bint &b) //Simple LCM Operation{return a / gcd(a, b) * b;}void read(const string &s) //Reading a Big Integer{sign = 1;a.clear();int pos = 0;while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {if (s[pos] == '-')sign = -sign;++pos;}for (int i = s.size() - 1; i >= pos; i -= base_digits) {int x = 0;for (int j = max(pos, i - base_digits + 1); j <= i; j++)x = x * 10 + s[j] - '0';a.push_back(x);}trim();}friend istream& operator>>(istream &stream, Bint &v) {string s;stream >> s;v.read(s);return stream;}friend ostream& operator<<(ostream &stream, const Bint &v) {if (v.sign == -1)stream << '-';stream << (v.a.empty() ? 0 : v.a.back());for (int i = (int) v.a.size() - 2; i >= 0; --i)stream << setw(base_digits) << setfill('0') << v.a[i];return stream;}static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {vector<long long> p(max(old_digits, new_digits) + 1);p[0] = 1;for (int i = 1; i < (int) p.size(); i++)p[i] = p[i - 1] * 10;vector<int> res;long long cur = 0;int cur_digits = 0;for (int i = 0; i < (int) a.size(); i++) {cur += a[i] * p[cur_digits];cur_digits += old_digits;while (cur_digits >= new_digits) {res.push_back(int(cur % p[new_digits]));cur /= p[new_digits];cur_digits -= new_digits;}}res.push_back((int) cur);while (!res.empty() && !res.back())res.pop_back();return res;}typedef vector<long long> vll;static vll karatsubaMultiply(const vll &a, const vll &b) //Multiplication using Karatsuba Algorithm{int n = a.size();vll res(n + n);if (n <= 32) {for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)res[i + j] += a[i] * b[j];return res;}int k = n >> 1;vll a1(a.begin(), a.begin() + k);vll a2(a.begin() + k, a.end());vll b1(b.begin(), b.begin() + k);vll b2(b.begin() + k, b.end());vll a1b1 = karatsubaMultiply(a1, b1);vll a2b2 = karatsubaMultiply(a2, b2);for (int i = 0; i < k; i++)a2[i] += a1[i];for (int i = 0; i < k; i++)b2[i] += b1[i];vll r = karatsubaMultiply(a2, b2);for (int i = 0; i < (int) a1b1.size(); i++)r[i] -= a1b1[i];for (int i = 0; i < (int) a2b2.size(); i++)r[i] -= a2b2[i];for (int i = 0; i < (int) r.size(); i++)res[i + k] += r[i];for (int i = 0; i < (int) a1b1.size(); i++)res[i] += a1b1[i];for (int i = 0; i < (int) a2b2.size(); i++)res[i + n] += a2b2[i];return res;}Bint operator*(const Bint &v) const {vector<int> a6 = convert_base(this->a, base_digits, 6);vector<int> b6 = convert_base(v.a, base_digits, 6);vll a(a6.begin(), a6.end());vll b(b6.begin(), b6.end());while (a.size() < b.size())a.push_back(0);while (b.size() < a.size())b.push_back(0);while (a.size() & (a.size() - 1))a.push_back(0), b.push_back(0);vll c = karatsubaMultiply(a, b);Bint res;res.sign = sign * v.sign;for (int i = 0, carry = 0; i < (int) c.size(); i++) {long long cur = c[i] + carry;res.a.push_back((int) (cur % 1000000));carry = (int) (cur / 1000000);}res.a = convert_base(res.a, 6, base_digits);res.trim();return res;}
};
int n;
Bint f[1005];signed main()
{cin>>n;f[0]=1;for(int i=1;i<=n*2;i++){f[i]=f[i-1]*i;}cout<<f[2*n]/(f[n]*f[n]*(n+1));return 0;
}P3978 [TJOI2015] 概率论
这题一看数据1e9大小，直接天塌了，这哪个方法也用不了了，只能想一下思维了，我们用
f[n]表示有n个节点的不同二叉树的个数，用s[n]表示n个节点拼成二叉树的叶子节点个数总和
我们f[n]其实就是卡特兰数，s[n]=n*f[n-1]，为什么这么算呢，因为每个二叉树都有n个地方可以插入，总共有f[n-1]个二叉树
然后用s[n]/f[n]，将f[n]=f[n-1]*(4*n-2)/(n-1)替换后，就得到最终式子
n*(n+1)/(4*n-2)AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
double n;
signed main()
{cin>>n;printf("%.10lf",n*(n+1)/(4*n-2));return 0;
}
