求助！！！怎么做？？？

题目总版

yangyanbin123 @ 2024-11-23 15:35:44

在圆上有 2∗n个不同的点，某人想用 n条线段把这些点连接起来（每个点只能连一条线段）,使所有的线段都不相交，他想知道这样的连接方案有多少种？

输入格式：一个正整数 n

输出格式：要求的方案数（结果 mod 100000007）

n<3000

动规！！！

by wang231064_YM @ 2024-11-23 15:58:13

直观的方法是使用卡特兰数（Catalan number）

附卡特兰数的通项公式： C_n = (1 / (n + 1)) * C(2n, n)。

根据卡特兰数的递推关系，我们有：dp[n] = dp[0] dp[n-1] + dp[1] dp[n-2] + ... + dp[n-1] * dp[0]

建议：n可能很大（n<3000），建议使用滚动数组以减少时间复杂度

by TeaQiLang @ 2024-11-23 16:16:39

#include<iostream>
using namespace std;
const int MOD = 100000007;
int dp[3001];
int main(){
    int n;
    cin>>n;
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2;i <= n;i++){
        for (int j = 0;j < i;j++){
            dp[i] = (dp[i] + (long long)dp[j] * dp[i - 1 - j]) % MOD;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

状态转移方程：dp[i] = (dp[i] + (long long)dp[j] * dp[i - 1 - j]) % MOD

by ikunTLE @ 2024-11-23 16:48:28

同楼上

f_i\gets f_i+f_j\times f_{i-j-1}

by 帝都_henry26268 @ 2024-11-23 16:52:46

猜你想要卡特兰数

by yangyanbin123 @ 2024-11-23 19:44:25

@TeaQiLang 谢谢！