题解：P10413 [蓝桥杯 2023 国 A] 圆上的连线

· · 题解

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

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

要在 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;
}