2023第十四届蓝桥杯国赛C/C++ 大学 A 组 圆上的连线

本文主要是介绍2023第十四届蓝桥杯国赛C/C++ 大学 A 组 圆上的连线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：很显然总的方案数等于挑选偶数点的方案数乘以对应偶数点的连线方案数之和，挑选偶数点的方案数靠组合数得出，偶数点的连线方案数就是个卡特兰数。具体为什么是卡特兰数，可以任选一个点，枚举这个点所连边的位置，这条边把点分为两部分，方案数等于这俩小部分各自方案数的乘积，结合卡特兰数的性质，

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=2023;
int f[2024]; 
int a[2028][2028];
signed main(){f[0]=1;f[1]=1;//求卡特兰数 for(int i=2;i<=1012;i++){for(int j=0;j<=i-1;j++){f[i]=(f[i]+f[j]*f[i-j-1]%mod)%mod;}}//求组合数 for(int i=0;i<=2023;i++){for(int j=0;j<=i;j++){if(j==0) a[i][j]=1;else{a[i][j]=(a[i-1][j]+a[i-1][j-1])%mod;}}}int ans=1; for(int i=2;i<=2022;i+=2){//选偶数个点的方案*偶数个点连线的方案 ans=(ans+a[2023][i]*f[i/2]%mod)%mod;}cout<<ans<<endl;return 0;
}

发现这就是卡特兰数。

这篇关于2023第十四届蓝桥杯国赛C/C++ 大学 A 组 圆上的连线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---