数据结构与算法：卡特兰数

WBluuue

485人浏览 · 2026-04-27 12:17:19

WBluuue · 2026-04-27 12:17:19 发布

前言

越来越变态了……

一、卡特兰数

0.内容

对于卡特兰数，有以下四个公式：

第一个： $f(n)=\binom{2n}{n}-\binom{2n}{n-1}$

第二个： $f(n)=\frac{\binom{2n}{n}}{n+1}$

第三个： $f(n)=\frac{f(n-1)\times (4n-2)}{n+1}$

第四个： $f(n)=\sum_{i=0}^{n-1}f(i)\times f(n-1-i)$

前三个公式求解的时间复杂度 O(n)，第四个公式求解的时间复杂度是 O(n^2)。其中对于第四个公式，需要知道卡特兰数的第零个和第一个数都是 1。

1.进出栈模型

规定进栈顺序是 1,2,3,...,n，随时都可以选择栈顶出栈，求出栈顺序的种数。

对于这个模型，其实是可以转化成正则括号匹配的问题。也就是说，将左括号看作进栈，将右括号看作出栈。此时问题就转化为，给定 n 个左括号和 n 个右括号，求合法的正则括号串的个数。

首先，若不考虑正则的问题，此时的方案数就是从 2n 个位置里选 n 个放左括号，即 $\binom{2n}{n}$ ，再减去不合法的方案数即可。那么对于不合法的方案数，考虑证明其和由 n-1 个左括号和 n+1 个右括号能拼出的方案数是一样的，即方案数 $\binom{2n}{n-1}$ 。

若将左括号看作 +1，右括号看作 -1，那么对于任意不合法的方案，其必然至少存在一个位置，使得其前缀和是小于 0 的。那么找到最左位置后，考虑翻转后续每个括号。此时由于是最左位置，且前缀和是线性增加的，所以此时前缀和必然等于 -1，即右括号比左括号多一个。也就是说，若左侧有 k 个左括号，就有 k+1 个右括号。那么右侧翻转后就有 n-k 个右括号，n-k-1 个左括号，相加就是 n-1 个左括号和 n+1 个右括号。所以将其还原回去后，后者的每个方案，必然对应前者的一个方案，所以两者构成满射关系。

而对于前者中两个不同的方案，其必然存在一个最左位置，使得两者在这个位置上不同。那么若最左违规的位置在这个位置的左侧，那么翻转后这个位置还是不同。否则，即最左违规的位置在这个位置右侧，那么翻转时左侧是不会发生变化的，这个位置还是会不同。所以前者的一个方案，必然对于后者的一个方案，两者也构成单射关系。所以两者构成双射，即两个问题是等价的。

所以进出栈模型的方案数就是卡特兰数的第一个公式。很多问题也符合这个模型。

比如，门票五元，初始卖票人手里没钱，n 个游客手里有五元，n 个游客手里有十元，求能保证找零的排队的方法数。这个问题其实就可以看作五元的人入栈，然后在十元的人来时往外弹出，所以跟上述模型是等价的。

再比如，圆上有 2n 个点，要求两两连接形成 n 条线段，求任意两线段不相交的方法数。此时可以发现，奇偶性相同的点是必然不能连接的。因为连接后就会导致中间有奇数个点，那么就必然有一个点需要往外连，那么就不合法了。所以就可以将奇数点看作进栈，弹出时就看作按顺序和偶数点相连。

2.路径计数模型

给定一个网格，从 (0,0) 出发要走到 (n,n) 点，每次只能在对角线及下方的区域里往上或往右走，求走到的方法数。

首先，对于总方案数，因为一定要往上走 n 步，往右走 n 步，所以就相当于在总的 2n 步里选 n 个位置往上走，方案数 $\binom{2n}{n}$ 。那么之后就需要找不合法的方案数，减一下即可。这里求不合法方案数的方法很重要！！

对于只能在对角线及以下区域走的限制，就可以转化成不能碰 (0,1) 到 (n-1,n) 这条违规斜线上的点。那么在左侧补出一列后，可以证明 不合法的方案数和从 (-1,1) 出发随意走到 (n,n) 的方案数是等价的。方法就是对于所有从 (-1,1) 出发任意走到 (n,n) 的路径，除了最后一次碰到违规斜线后走的路径，将其他部分以违规斜线为轴翻转，此时可以发现其就是一条从 (0,0) 点出发到 (n,n) 点的违规路径。此时由于从 (-1,1) 出发的方案数就是 $\binom{2n}{n-1}$ ，所以结果就是 $\binom{2n}{n}-\binom{2n}{n-1}$ 。

可以发现，若出现了违规情况，那么必然存在一个时刻，向上走的次数大于了向左走的次数。那么就可以将向左走看作左括号，向上走看作右括号，这就转化成第一个模型了。那么类似的，对于 n 个左括号和 m 个右括号的问题，也可以通过转化成路径计数模型解决。

这个方法可以推广到很多问题中，比如从 (0,0) 走到 (n,n) 点，每次只能往上或往右走，不能碰对角线的方法数。对于这个问题，首先可以发现第一步向右和向上走，会导致之后只能在那一半区活动。又因为是对称的，所以求出一个后乘二即可。首先，总方案数就是 $\binom{2n-2}{n-1}$ ，即从 (0,1) 走到 (n-1,n) 的方案数。之后，还是考虑翻转，那么可以发现此时的不合法方案数，就是从 (1,0) 出发随意走到 (n-1,n) 的方案数。证明还是 除了最后一次碰到对角线后的路径，前面部分全以对角线为轴翻转，就是从 (0,1) 出发的违规路径。所以这个的方案数就是 $\binom{2n-2}{n-2}$ ，最后相减乘二即可。

3.划分左右相乘模型

给定一个 n+2 边形，求通过顶点相连，将这个多边形划分为若干个三角形，其中连线不能相交的方案数。

对于 n+2 边形，设 f(n) 为最终答案。那么此时就可以选择固定两个点，然后去讨论和哪个点一起形成一个三角形。对于每种情况，之后就是去左右两侧求 f(left) 和 f(right)，然后相乘即可，其中 left 和 right 分别表示左右的答案。此时就是划分左右相乘问题，可以发现对应的就是卡特兰数的第四个公式，即 $f(n)=\sum_{i=0}^{n-1}f(i)\times f(n-1-i)$ 。

其实区间 dp 好像也能写（）

再就是给定 n 个节点，认为节点和节点相同，求能构建出的不同的二叉树个数。那么在规定一个节点为根后，每次可以选择左侧有 i 个节点，右侧有 n-1-i 个节点，然后两侧相乘累加。又因为当有 1 个和 2 个节点时方案数都是 1，所以这个显然就是卡特兰数了。

4.取模处理

首先，若 $n\leq35$ ，此时答案是不会溢出的，所以一般不会给模数，那么此时就只能使用第四个公式。因为前两个公式涉及阶乘，第三个公式是由一个很大的数除下来的，会发生溢出，所以只能使用第四个公式。类似的，若给定的模数不是质数，同样也只能用第四个公式。

重点是，当 n 很大，且模数不是质数时，此时第四个公式必然会导致超时，所以就只能使用前三个公式。此时，就涉及到因子计数法了。

对于第三个公式，有 $f(n)=\frac{\binom{2n}{n}}{n+1}=\frac{(2n)!}{n!\times n!\times n+1}$ ，消一下就有 $f(n)=\frac{(n+2)\times (n+3)\times ...\times 2n}{2\times 3\times ...\times n}$ 。之后，考虑通过筛法构建出最小质因子表，即对每个合数存其最小的质因子。然后在因子计数数组中，先给分母上每个数的位置标 -1，分子上每个数的位置标 +1。之后从大到小考虑每个数，对于当前数，若是合数的话，设其词频为 c，那么就将其分解成其最小质因子 p 和另一部分 x，再给这两个数的词频都 +c，然后清空当前合数的词频，即分解其对答案的贡献。最后再根据每个质数的词频，把这些数都乘起来即可。

二、题目

1.栈

上次提交还是一年以前，当时的代码好稚嫩哈哈！

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

template<class T>
constexpr T power(T a, ll b) {
    T res = 1;
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

template<int M>
struct ModInt {
public:
    constexpr ModInt() : x(0) {}

    template<typename T>
    constexpr ModInt(T x_) {
        T v = x_ % M;
        if (v < 0) {
            v += M;
        }
        x = v;
    }
 
    constexpr int val() const {
        return x;
    }

    constexpr ModInt &operator++() & {
        x++;
        if (x == M) {
            x = 0;
        }
        return *this;
    }

    constexpr ModInt operator++(int) & {
        ModInt res = *this;
        ++(*this);
        return res;
    }

    constexpr ModInt &operator--() & {
        if (x == 0) {
            x = M - 1;
        } else {
            x--;
        }
        return *this;
    }

    constexpr ModInt operator--(int) & {
        ModInt res = *this;
        --(*this);
        return res;
    }
 
    constexpr ModInt operator-() const {
        ModInt res;
        res.x = (x == 0 ? 0 : M - x);
        return res;
    }
 
    constexpr ModInt inv() const {
        return power(*this, M - 2);
    }
 
    constexpr ModInt &operator*=(const ModInt &rhs) &{
        x = ll(x) * rhs.val() % M;
        return *this;
    }
 
    constexpr ModInt &operator+=(const ModInt &rhs) &{
        x += rhs.val();
        if (x >= M) {
            x -= M;
        }
        return *this;
    }
 
    constexpr ModInt &operator-=(const ModInt &rhs) &{
        x -= rhs.val();
        if (x < 0) {
            x += M;
        }
        return *this;
    }
 
    constexpr ModInt &operator/=(const ModInt &rhs) &{
        return *this *= rhs.inv();
    }
 
    friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) {
        lhs *= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) {
        lhs += rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) {
        lhs -= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) {
        lhs /= rhs;
        return lhs;
    }
 
    friend constexpr bool operator==(ModInt lhs, const ModInt &rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator<(ModInt lhs, const ModInt &rhs) {
        return lhs.val() < rhs.val();
    }
    
    friend constexpr bool operator>(ModInt lhs, const ModInt &rhs) {
        return lhs.val() > rhs.val();
    }
    
    friend constexpr bool operator<=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() <= rhs.val();
    }
    
    friend constexpr bool operator>=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() >= rhs.val();
    }
    
    friend constexpr bool operator!=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() != rhs.val();
    }
 
    friend constexpr std::istream &operator>>(std::istream &is, ModInt &a) {
        ll i;
        is >> i;
        a = i;
        return is;
    }
 
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt &a) {
        return os << a.val();
    }
 
private:
    int x;
};

template<int M, typename T = ModInt<M>>
struct Comb {
    vector<T> fac;
    vector<T> inv;
 
    Comb(int n) {
        fac.assign(n, 1);
        for(int i=1;i<n;i++)
        {
            fac[i]=fac[i-1]*i;
        }
        inv.assign(n, 1);
        inv[n-1]=fac[n-1].inv();
        for(int i=n-2;i>=0;i--)
        {
            inv[i]=inv[i+1]*(i+1);
        }
    }
 
    template<std::signed_integral U>
    T P(U n, U m) {
        if(n<m)
        {
            return 0;
        }
        return fac[n] * inv[n - m];
    }
 
    template<std::signed_integral U>
    T C(U n, U m) {
        if(n<m||m<0)
        {
            return 0;
        }
        return fac[n] * inv[n - m] * inv[m];
    }
};
 
//power函数切记强转成 Z !!!!!
constexpr int M = 998244353;
using Z = ModInt<M>;

constexpr int N = 2e5+5;
Comb<M>comb(N);

template<std::signed_integral U>
Z P(U n, U m) {
    return comb.P(n, m);
}
 
template<std::signed_integral U>
Z C(U n, U m) {
    return comb.C(n, m);
}

void solve()
{
    int n;
    cin>>n;
    
    Z ans=C(2*n,n)-C(2*n,n-1);
    cout<<ans<<endl;
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

没啥好说的，直接套第一个公式即可。

2.鸡蛋饼

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

template<class T>
constexpr T power(T a, ll b) {
    T res = 1;
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

template<int M>
struct ModInt {
public:
    constexpr ModInt() : x(0) {}

    template<typename T>
    constexpr ModInt(T x_) {
        T v = x_ % M;
        if (v < 0) {
            v += M;
        }
        x = v;
    }
 
    constexpr int val() const {
        return x;
    }

    constexpr ModInt &operator++() & {
        x++;
        if (x == M) {
            x = 0;
        }
        return *this;
    }

    constexpr ModInt operator++(int) & {
        ModInt res = *this;
        ++(*this);
        return res;
    }

    constexpr ModInt &operator--() & {
        if (x == 0) {
            x = M - 1;
        } else {
            x--;
        }
        return *this;
    }

    constexpr ModInt operator--(int) & {
        ModInt res = *this;
        --(*this);
        return res;
    }
 
    constexpr ModInt operator-() const {
        ModInt res;
        res.x = (x == 0 ? 0 : M - x);
        return res;
    }
 
    constexpr ModInt inv() const {
        return power(*this, M - 2);
    }
 
    constexpr ModInt &operator*=(const ModInt &rhs) &{
        x = ll(x) * rhs.val() % M;
        return *this;
    }
 
    constexpr ModInt &operator+=(const ModInt &rhs) &{
        x += rhs.val();
        if (x >= M) {
            x -= M;
        }
        return *this;
    }
 
    constexpr ModInt &operator-=(const ModInt &rhs) &{
        x -= rhs.val();
        if (x < 0) {
            x += M;
        }
        return *this;
    }
 
    constexpr ModInt &operator/=(const ModInt &rhs) &{
        return *this *= rhs.inv();
    }
 
    friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) {
        lhs *= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) {
        lhs += rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) {
        lhs -= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) {
        lhs /= rhs;
        return lhs;
    }
 
    friend constexpr bool operator==(ModInt lhs, const ModInt &rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator<(ModInt lhs, const ModInt &rhs) {
        return lhs.val() < rhs.val();
    }
    
    friend constexpr bool operator>(ModInt lhs, const ModInt &rhs) {
        return lhs.val() > rhs.val();
    }
    
    friend constexpr bool operator<=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() <= rhs.val();
    }
    
    friend constexpr bool operator>=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() >= rhs.val();
    }
    
    friend constexpr bool operator!=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() != rhs.val();
    }
 
    friend constexpr std::istream &operator>>(std::istream &is, ModInt &a) {
        ll i;
        is >> i;
        a = i;
        return is;
    }
 
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt &a) {
        return os << a.val();
    }
 
private:
    int x;
};

template<int M, typename T = ModInt<M>>
struct Comb {
    vector<T> fac;
    vector<T> inv;
 
    Comb(int n) {
        fac.assign(n, 1);
        for(int i=1;i<n;i++)
        {
            fac[i]=fac[i-1]*i;
        }
        inv.assign(n, 1);
        inv[n-1]=fac[n-1].inv();
        for(int i=n-2;i>=0;i--)
        {
            inv[i]=inv[i+1]*(i+1);
        }
    }
 
    template<std::signed_integral U>
    T P(U n, U m) {
        if(n<m)
        {
            return 0;
        }
        return fac[n] * inv[n - m];
    }
 
    template<std::signed_integral U>
    T C(U n, U m) {
        if(n<m||m<0)
        {
            return 0;
        }
        return fac[n] * inv[n - m] * inv[m];
    }
};
 
//power函数切记强转成 Z !!!!!
constexpr int M = 1e8+7;
using Z = ModInt<M>;

constexpr int N = 2e5+5;
Comb<M>comb(N);

template<std::signed_integral U>
Z P(U n, U m) {
    return comb.P(n, m);
}
 
template<std::signed_integral U>
Z C(U n, U m) {
    return comb.C(n, m);
}

void solve()
{
    int n;
    cin>>n;

    Z ans=C(2*n,n)/(n+1);
    cout<<ans<<endl;
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

这个还是进出栈模型，这里用的是第二个公式。

3.矩阵 II

byd 原来第四个公式的优势区间是这个……

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

const int MOD=100;

void solve()
{
    int n;
    cin>>n;

    vector<ll>f(n+1);
    f[0]=f[1]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=i-1;j++)
        {
            f[i]=(f[i]+f[j]*f[i-1-j]%MOD)%MOD;
        }
    }
    cout<<f[n]<<endl;
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

因为模数是 100，那么所有涉及除法逆元的公式都不能用了，而且 exgcd 也要求两数必须互质。那么此时就只能用第四个公式了，因为不涉及除法。注意递推时下标不是 n 是 i，不要混淆了！！

4.不同的二叉搜索树

class Solution {
public:
    int numTrees(int n) {
        vector<int>f(n+1);
        f[0]=f[1]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=i-1;j++)
            {
                f[i]+=f[j]*f[i-1-j];
            }
        }
        return f[n];
    }
};

因为 n 很小，所以直接放空大脑暴力即可（）

5.有趣的数列

md 这题只有绿？？！

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

ll power(ll x,ll n,ll p)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
        {
            ans=ans*x%p;
        }

        x=x*x%p;
        n>>=1;
    }
    return ans;
}

void solve()
{
    ll n,p;
    cin>>n>>p;

    vector<int>minp(2*n+1);
    for(ll i=2;i<=2*n;i++)
    {
        if(!minp[i])
        {
            for(ll j=2*i;j<=2*n;j+=i)
            {
                if(!minp[j])
                {
                    minp[j]=i;
                }
            }
        }
    }

    vector<int>cnts(2*n+1);
    for(int i=2;i<=n;i++)
    {
        cnts[i]=-1;
    }
    for(int i=n+2;i<=2*n;i++)
    {
        cnts[i]=1;
    }

    for(int i=2*n;i>=2;i--)
    {
        if(minp[i])
        {
            cnts[minp[i]]+=cnts[i];
            cnts[i/minp[i]]+=cnts[i];
            cnts[i]=0;
        }
    }

    ll ans=1;
    for(int i=2;i<=2*n;i++)
    {
        ans=ans*power(i,cnts[i],p)%p;
    }
    cout<<ans<<endl;
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

byd 这个题你得先转化出卡特兰数……

可以发现直接考虑不是很好想，那么 对于计数问题，推不动时考虑转换视角。所以将视角改变成从每个数字入手，考虑其能填到什么位置。之后考虑从 1 开始顺着填，既然要求奇数位和偶数位的内部是递增的，那么不管当前数字要填到奇数位还是偶数位，其都应该填到对应的最左的空位。那么对于这 2n 个数，必然有 n 次填到奇数位，有 n 次填到偶数位，方案数 $\binom{2n}{n}$ 。

又因为有偶数项要大于前一个奇数项的限制，那么在填的时候，若当前选择填到偶数项里，就必然保证其前面所有奇数项都被填过了。否则因为后续都是大于当前数的数，那么就必然会导致前一位奇数项上的数大于当前偶数项上的数。所以，对于每个选择填入偶数项的操作，其必须保证前面之前选择填入奇数项的次数，大于等于选择填入偶数项的次数。那么这个过程就可以转化为正则括号匹配，将填入奇数项看作左括号，填入偶数项看作右括号。所以上述条件就等价于要求这个括号串正则，那么这个的方案数就是卡特兰数了。

之后由于模数任意，所以要用因子计数法处理。

这题又是视角转换，又是卡特兰数建模，最后还要想办法处理合数模数，这能只是个绿？？这不至少是个蓝？？！！

6.生成字符串

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

template<class T>
constexpr T power(T a, ll b) {
    T res = 1;
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

template<int M>
struct ModInt {
public:
    constexpr ModInt() : x(0) {}

    template<typename T>
    constexpr ModInt(T x_) {
        T v = x_ % M;
        if (v < 0) {
            v += M;
        }
        x = v;
    }
 
    constexpr int val() const {
        return x;
    }

    constexpr ModInt &operator++() & {
        x++;
        if (x == M) {
            x = 0;
        }
        return *this;
    }

    constexpr ModInt operator++(int) & {
        ModInt res = *this;
        ++(*this);
        return res;
    }

    constexpr ModInt &operator--() & {
        if (x == 0) {
            x = M - 1;
        } else {
            x--;
        }
        return *this;
    }

    constexpr ModInt operator--(int) & {
        ModInt res = *this;
        --(*this);
        return res;
    }
 
    constexpr ModInt operator-() const {
        ModInt res;
        res.x = (x == 0 ? 0 : M - x);
        return res;
    }
 
    constexpr ModInt inv() const {
        return power(*this, M - 2);
    }
 
    constexpr ModInt &operator*=(const ModInt &rhs) &{
        x = ll(x) * rhs.val() % M;
        return *this;
    }
 
    constexpr ModInt &operator+=(const ModInt &rhs) &{
        x += rhs.val();
        if (x >= M) {
            x -= M;
        }
        return *this;
    }
 
    constexpr ModInt &operator-=(const ModInt &rhs) &{
        x -= rhs.val();
        if (x < 0) {
            x += M;
        }
        return *this;
    }
 
    constexpr ModInt &operator/=(const ModInt &rhs) &{
        return *this *= rhs.inv();
    }
 
    friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) {
        lhs *= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) {
        lhs += rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) {
        lhs -= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) {
        lhs /= rhs;
        return lhs;
    }
 
    friend constexpr bool operator==(ModInt lhs, const ModInt &rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator<(ModInt lhs, const ModInt &rhs) {
        return lhs.val() < rhs.val();
    }
    
    friend constexpr bool operator>(ModInt lhs, const ModInt &rhs) {
        return lhs.val() > rhs.val();
    }
    
    friend constexpr bool operator<=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() <= rhs.val();
    }
    
    friend constexpr bool operator>=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() >= rhs.val();
    }
    
    friend constexpr bool operator!=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() != rhs.val();
    }
 
    friend constexpr std::istream &operator>>(std::istream &is, ModInt &a) {
        ll i;
        is >> i;
        a = i;
        return is;
    }
 
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt &a) {
        return os << a.val();
    }
 
private:
    int x;
};

template<int M, typename T = ModInt<M>>
struct Comb {
    vector<T> fac;
    vector<T> inv;
 
    Comb(int n) {
        fac.assign(n, 1);
        for(int i=1;i<n;i++)
        {
            fac[i]=fac[i-1]*i;
        }
        inv.assign(n, 1);
        inv[n-1]=fac[n-1].inv();
        for(int i=n-2;i>=0;i--)
        {
            inv[i]=inv[i+1]*(i+1);
        }
    }
 
    template<std::signed_integral U>
    T P(U n, U m) {
        if(n<m)
        {
            return 0;
        }
        return fac[n] * inv[n - m];
    }
 
    template<std::signed_integral U>
    T C(U n, U m) {
        if(n<m||m<0)
        {
            return 0;
        }
        return fac[n] * inv[n - m] * inv[m];
    }
};
 
//power函数切记强转成 Z !!!!!
constexpr int M = 20100403;
using Z = ModInt<M>;

constexpr int N = 2e6+5;
Comb<M>comb(N);

template<std::signed_integral U>
Z P(U n, U m) {
    return comb.P(n, m);
}
 
template<std::signed_integral U>
Z C(U n, U m) {
    return comb.C(n, m);
}

void solve()
{
    int n,m;
    cin>>n>>m;

    Z ans=C(n+m,n)-C(n+m,n+1);
    cout<<ans<<endl;
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

对于这种不能存在一个时刻，使得 A 的次数大于 B 的次数的问题，还是往卡特兰数方向考虑。

因为这里有 n 个 1 和 m 个 0，没法直接套用第一个模型，所以考虑将其转化成第二个模型。考虑将 1 看作向右组，将 0 看作向上走，那么问题就变为，从 (0,0) 点走到 (n,m) 点，不能碰到从 (1,1) 开始向斜上方的斜率为 1 的这条直线的方案数。

首先，总路径就是 $\binom{n+m}{n}$ ，之后考虑违规的路径。所以还是不考虑最后一次碰到这条线之后的路径，将前面的路径以这条线为轴翻转，那么就转化为从 (-1,1) 走到 (n,m) 的一条路径。所以违规的方案数，就是 $\binom{n+m}{n+1}$ 。

7.Skyline

左神都找不到合理的解释，这也太草了……

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

template<class T>
constexpr T power(T a, ll b) {
    T res = 1;
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

template<int M>
struct ModInt {
public:
    constexpr ModInt() : x(0) {}

    template<typename T>
    constexpr ModInt(T x_) {
        T v = x_ % M;
        if (v < 0) {
            v += M;
        }
        x = v;
    }
 
    constexpr int val() const {
        return x;
    }

    constexpr ModInt &operator++() & {
        x++;
        if (x == M) {
            x = 0;
        }
        return *this;
    }

    constexpr ModInt operator++(int) & {
        ModInt res = *this;
        ++(*this);
        return res;
    }

    constexpr ModInt &operator--() & {
        if (x == 0) {
            x = M - 1;
        } else {
            x--;
        }
        return *this;
    }

    constexpr ModInt operator--(int) & {
        ModInt res = *this;
        --(*this);
        return res;
    }
 
    constexpr ModInt operator-() const {
        ModInt res;
        res.x = (x == 0 ? 0 : M - x);
        return res;
    }
 
    constexpr ModInt inv() const {
        return power(*this, M - 2);
    }
 
    constexpr ModInt &operator*=(const ModInt &rhs) &{
        x = ll(x) * rhs.val() % M;
        return *this;
    }
 
    constexpr ModInt &operator+=(const ModInt &rhs) &{
        x += rhs.val();
        if (x >= M) {
            x -= M;
        }
        return *this;
    }
 
    constexpr ModInt &operator-=(const ModInt &rhs) &{
        x -= rhs.val();
        if (x < 0) {
            x += M;
        }
        return *this;
    }
 
    constexpr ModInt &operator/=(const ModInt &rhs) &{
        return *this *= rhs.inv();
    }
 
    friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) {
        lhs *= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) {
        lhs += rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) {
        lhs -= rhs;
        return lhs;
    }
 
    friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) {
        lhs /= rhs;
        return lhs;
    }
 
    friend constexpr bool operator==(ModInt lhs, const ModInt &rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator<(ModInt lhs, const ModInt &rhs) {
        return lhs.val() < rhs.val();
    }
    
    friend constexpr bool operator>(ModInt lhs, const ModInt &rhs) {
        return lhs.val() > rhs.val();
    }
    
    friend constexpr bool operator<=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() <= rhs.val();
    }
    
    friend constexpr bool operator>=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() >= rhs.val();
    }
    
    friend constexpr bool operator!=(ModInt lhs, const ModInt &rhs) {
        return lhs.val() != rhs.val();
    }
 
    friend constexpr std::istream &operator>>(std::istream &is, ModInt &a) {
        ll i;
        is >> i;
        a = i;
        return is;
    }
 
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt &a) {
        return os << a.val();
    }
 
private:
    int x;
};

template<int M, typename T = ModInt<M>>
struct Comb {
    vector<T> fac;
    vector<T> inv;
 
    Comb(int n) {
        fac.assign(n, 1);
        for(int i=1;i<n;i++)
        {
            fac[i]=fac[i-1]*i;
        }
        inv.assign(n, 1);
        inv[n-1]=fac[n-1].inv();
        for(int i=n-2;i>=0;i--)
        {
            inv[i]=inv[i+1]*(i+1);
        }
    }
 
    template<std::signed_integral U>
    T P(U n, U m) {
        if(n<m)
        {
            return 0;
        }
        return fac[n] * inv[n - m];
    }
 
    template<std::signed_integral U>
    T C(U n, U m) {
        if(n<m||m<0)
        {
            return 0;
        }
        return fac[n] * inv[n - m] * inv[m];
    }
};
 
//power函数切记强转成 Z !!!!!
constexpr int M = 1000000;
using Z = ModInt<M>;

constexpr int N = 2e5+5;
Comb<M>comb(N);

template<std::signed_integral U>
Z P(U n, U m) {
    return comb.P(n, m);
}
 
template<std::signed_integral U>
Z C(U n, U m) {
    return comb.C(n, m);
}

const int MAXN=1000;

vector<Z>catalan(MAXN+1);

void solve()
{
    while(true)
    {
        int n;
        cin>>n;

        if(n==0)
        {
            break;
        }

        cout<<catalan[n]<<endl;
    }
}

void init()
{
    catalan[0]=catalan[1]=1;
    for(int i=2;i<=MAXN;i++)
    {
        for(int j=0;j<=i-1;j++)
        {
            catalan[i]+=catalan[j]*catalan[i-1-j];
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

因为不能出现 123 模式的子序列，所以若 i 位置上的数是前缀最小值，那么其后面不是前缀最小值的所有数必然要求降序排列。因为如果存在一个位置是升序的，那么其必然可以跟在前缀最小值的后面，形成 123 模式的子序列，所以是不合法的。

那么对于当前填到的位置 i，若此时的前缀最小值为 x，那么就要求大于等于 x 的个数 n-x+1，要大于等于当前位置 i，否则这个数就不可能是前缀最小值。那么对于这个问题，将填一个位置看作向上走，将当前前缀最小值 x 看作向右走到 n-x+1 位置。因为前缀最小值单调不增，所以向右走到的位置单调不减，那么就可以转化成路径计数问题了，所以答案就是卡特兰数。

8.树屋阶梯

什么傻逼题考高精度……

n=int(input())

catalan=[0 for _ in range(n+1)]

catalan[0]=catalan[1]=1

for i in range(2,n+1):
    for j in range(0,i):
        catalan[i]+=catalan[j]*catalan[i-1-j]

print(catalan[n])

由样例可以获得启发，考虑枚举当前划分。那么就是从左下角点开始，选择一个覆盖掉某个角的矩形，那么就把整个阶梯划分成上下两个小阶梯了，相乘即可。

嘿嘿 python 嘿嘿（）

9.概率论

概率期望屋檐了……

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

void solve()
{
    double n;
    cin>>n;

    cout<<fixed<<setprecision(10)<<( n*(n+1)/((2*n-1)*2) )<<endl;
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

对于期望，肯定就是所有结构中叶子节点的总数，除以所有可能的结构数。对于后者，就是卡特兰数，但因为 n 很大，所以不能直接求，需要考虑化简。

打表可以发现，对于 n-1 个节点能下形成的所有可能的结构数 f(n-1)，此时若想插入一个节点变成 n 个节点能形成的结构，则必然有 n 个可以插入的位置。那么对于 n 个节点能形成的所有结构中叶子节点的总数 g(n)，这 n 种方案每种都可以产生一点贡献，所以就有 $g(n)=n\times f(n-1)$ 。又因为答案是 $\frac{g(n)}{f(n)}$ ，通过卡特兰数第二个公式化简就有 $\frac{\binom{2n-2}{n-1}}{\binom{2n}{n}}\times (n+1)$ ，再对两个组合数化简就有 $\frac{n\times n}{(2n-1)\times 2n}\times (n+1)$ ，再化简就有 $\frac{n\times (n+1)}{(2n-1)\times 2}$ ，即答案。

总结

这卡特兰数建模不亚于图论建模啊，好难……

END

乐奇 Rokid 开放社区

更多推荐

哪个家电企业综合技术全球领先？看TCL白电

挑冰箱时，这正是判断一个品牌的冰箱值不值得买的地方。在AI应用之外，面向AI时代，又将AI技术落到产品深处，打造AR智能眼镜、家庭「陪 · 育」机器人、智能电视、AI空调、AI洗衣机、AI冰箱等多产品线，在智能制造和智能生活上深度布局。回头看，TCL家电的技术不在于某一句宣传语，而在于一台电视的显示技术、一台冰箱的冷凝器、一台空调的变频控制器、一台洗衣机的传感器等细节里。一台家电好不好，往往不由