当前位置：首页 > news >正文

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

news 来源：原创 2025/8/28 15:55:32

题意：

给定一个圆，圆上有 n=2023 个点从 1 到 n 依次编号。

问有多少种不同的连线方式，使得完全没有连线相交。当两个方案连线的数量不同或任何一个点连接的点在另一个方案中编号不同时，两个方案视为不同。

答案可能很大，请将答案对 2023 求余后提交。

思路：

首先是卡特兰数，然后没了，G32 卡特兰数_哔哩哔哩_bilibili，如果不理解，可以看这个视频，这道题其实就是视频中的拓展，加了个组合数选多少个点而已。

理解： 首先这个理解很可能有问题，如果你有更好的想法，请一定要在评论里告诉我，因为我现在都还是不太确定我的理解是否正确。

我看了很多关于卡特兰数的，看完之后感觉都像是感觉，没有一个确切的说怎么怎么样就是卡特兰数，因此我目前把卡特兰数归纳为
一个问题在任何子集情况下，违规操作的条件是不变动的，执行违规操作后，无论后面是什么样的，一定是错误，那么就是卡特兰数的使用范畴。
例如这道选点，违规操作就是不能选择穿越区间的点，无论你进行到哪一步怎么划分都是这个条件，即不能穿过上一条线选点。
如果是出入栈问题，那么无论你进行了多少步，只要出栈操作次数超过入栈那么就是错误，无论在哪个子集，哪一步，都是这个条件。
如果是二叉树，无论进行到哪一步，都不能连接已经连接过的点，这就是违规操作。
如果是连接顶点，无论到哪一步，都必须在选好一个节点去连新的边，只要不符合这个要求，就会错。
如果是斜线问题，无论到那一步，目前移动到的点不能超过斜边。
无论在哪个自己情况下，条件不能发生变动，他是固定的。不需要分情况讨论，无论在什么情况下都是一个要求，那就会是卡特兰数。
判断方式就是一道题的成功构造，是不是被一个固定条件限制住了，如果限制住，那很可能是卡特兰数。

请注意：该方法完全是类似于数学归纳法，看了一些之后自己想出来的一个方式，本人完全想不出数学或者说正经的方式，而网上大抵也没找到几个严格指出的，都是感觉，或者类比，但是本人思维理解不了是怎么归到一类的。比如这个圆圈选点跟斜线，我看不出相同点，所以自己思考归纳出来的这个相同点。非常不严格，请不要沿用这个方式。

说出这个归纳仅仅是希望后来有能力的人看到后，请来指正我，告诉我到底应该怎么思考更正确。
有参考：
1.题解：P10413 [蓝桥杯 2023 国 A] 圆上的连线 - 洛谷专栏
2.「算法入门笔记」卡特兰数 - 知乎
个人认为2的想法非常好，很有说服力，但是我认为这个圆上选点，我很难联系到这个+1,-1，所以引出了这个自己的思考方法,其实跟+1，-1也挺像的……我只是觉得那个圆圈选点归纳到选栈真的有点异想天开的赶脚，有一点强行……

那么回到代码，非常简单，预处理组合数和卡特兰数，卡特兰数是一个递推公式，至于怎么推导出来的……我也不会。
组合数预处理方式是帕斯卡法则，这里顺带推荐一下用到这个性质的好题【补题】Codeforces Global Round 21 E. Placing Jinas-CSDN博客
组合数的累加、杨辉三角就可以往这个方向思考
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 2023;int C[2025][2025];
int H[2025];void solve(){int n=2023;for(int i=0;i<=2023;i++) C[i][0]=C[i][i]=1;for(int i=0;i<=2023;i++){for(int j=1;j<=i;j++){C[i][j]=(C[i-1][j]+C[i-1][j-1])%2023;}}H[0]=H[1]=1;for(int i=2;i<=2023;i++){for(int j=0;j<i;j++){H[i]=(H[i]+(H[j]*H[i-j-1]+MOD)%MOD)%MOD;}}int res=0;for(int i=0;i<=2023;i+=2){res=(res+(C[2023][i]*H[i/2]%MOD))%MOD;}cout << (res+MOD)%MOD << endl;
}signed main(){IOS;int t=1;
//	cin >> t;while(t--){solve();}
}

相关文章：