自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:57:44，当前版本为作者最后更新于2024-05-10 00:10:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

引子：本题目前已有题解写的都挺滑稽的，全是“显然”、“可知”，但是看题解的人大概都是没有看出来卡特兰数的人。因此，我写这一篇题解，希望能帮助读者理解。

前置知识：卡特兰数。如果不会的同学可以看下面这个视频：

要在 $2023$ 个点中选任一些点进行连线，因为每个点最多只能连出一条线，所以每次选的点数一定是一个偶数。

假设选 $n$ 个点的方案数为 $a_n$，此时答案为 $b_n$，易得最终答案为 $\displaystyle\sum^{2023}_{i=1}\left[i \equiv 0\left(\bmod 2\right)\right]a_i b_i$。方案数 $a_n$ 代表从 $2023$ 个点中选出 $n$ 个点的方案数，可以看出是组合数 $C_{2023}^n$，那么问题就变成了如何求 $b_n$。其实 $b_n$ 的求法在题解最开始的视频中已经有了讲解，如果没看懂可以看下面的分析：

令 $n=2x\left(x\in\N^*\right)$ ，对于任意一个点，所有合法的连出去的线，一定要把其余的点分成两个区域，且两个区域的点均为偶数个。令 $f(x)$ 表示点数为 $2x$ 时的连法，有 $f(x)=f(0)\times f(x-1)+f(1)\times f(x-2)+\dots+f(x-1)\times f(0)$。可以发现是卡特兰数，一般表示为 $H_n$。
常见通项公式有 $3$ 种，分别是：$\normalsize H_n=C^{n}_{2n}-C^{n-1}_{2n}\tiny{\colorbox{yellow}{[1]}}\normalsize=\frac{1}{n+1}C^{n}_{2n}\tiny{\colorbox{yellow}{[2]}}=\normalsize\frac{4n-2}{n+1}H_{n-1}\tiny{\colorbox{yellow}{[3]}}$。题解开头的视频中有详细的证明，这里不再赘述。

带入 $a_n=C_{2023}^n,b_n=H_{\frac{n}{2}}$，可知答案为 $\displaystyle\sum^{2023}_{i=1}\left[i \equiv 0\left(\bmod 2\right)\right]C_{2023}^iH_{\frac{i}{2}}$（其中 $H_n$ 代表卡特兰数第 $n$ 项）。

组合数和卡特兰数的计算可以使用预处理，不要忘记对 $2023$ 取余，代码如下，答案为 104。

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