题目

思路

因为不相交，所以每个点最多连出一条线，所以参与连线的点一定是偶数个

我们按照选出点的数量 2，4 …… 2x 将答案划分，答案可以表示为

（假设我们选出2x个点连线，假设方法数为 ：2x个点参与连线的方案数）

如果我们确定一条线，还剩下  组，这条线肯定把剩下的  个点分成两个偶数点块（这样每个子块内才能继续完成连线）

于是问题就被划分为  

                                                                                                                        ——卡特兰数

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2023 + 10, mod = 2023;
int h[N] = {1, 1};
int c[N][N];
int main()
{int n = 2023;for(int i = 0; i <= n; i++)c[i][0] = 1;for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;for(int i = 2; i <= n; i++)for(int j = 0; j < i; j++)h[i] = (h[i] + h[j] * h[i-1-j]) % mod;int ans = 1;for(int i = 2; i <= n; i++)if(i % 2 == 0)ans = (ans + c[n][i] * h[i/2]) % mod;cout << ans;
}