ToB企服应用市场:ToB评测及商务社交产业平台

标题: 洛谷 P8705：[蓝桥杯 2020 省 B1] 填空题之“试题 E ：矩阵” ← 卡特兰数 [打印本页]

作者: 河曲智叟 时间: 3 天前
标题: 洛谷 P8705：[蓝桥杯 2020 省 B1] 填空题之“试题 E ：矩阵” ← 卡特兰数
【题目泉源】
https://www.luogu.com.cn/problem/P8705

【题目形貌】
把 1∼2020 放在 2×1010 的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案?
答案很大，你只必要给出方案数除以 2020 的余数即可。

【答案提交】
这是一道结果填空题，你只必要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【算法分析】
● 卡特兰数（Catalan number）是组合数学中一个常出现在各种计数问题中的数列。若从第 0 项开始，则卡特兰数列 h[n] 为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, …。

● 常用的卡特兰数列 h[n] 有如下 4 种等价的递推式
h[n]=h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0], (n≥2, h[0]=h[1]=1)
h[n]=h[n−1]*(4*n−2)/(n+1), (n≥2)
h[n]=C(2n,n)−C(2n,n−1), (n=0,1,2,...)
h[n]=C(2n,n)/(n+1), (n=0,1,2,...)

● 卡特兰数的第 20 项为 6564120420，大于 2×10^9，所以代码中要声明为 long long 型。

● 矩阵添补与进栈出栈过程的对应关系以及和卡特兰数的联系
（1）第一行添补对应进栈：当我们从左到右添补矩阵的第一行时，每放入一个数字，就相称于一个元素进栈。由于第一行的数字是依次增大的，就似乎元素依次进入栈中，且栈内元素是按照进栈次序依次分列（从小到大）。
（2）第二行添补对应出栈：当我们开始添补矩阵的第二行时，由于要满足同一列下边的数字比上边大，所以放入第二行的数字必须是已经在第一行出现过的数字，这就类似于元素出栈。

（3）可以将进栈（push）利用看作在平面直角坐标系中向沿 x 轴正向走一步，出栈（pop）利用看作沿 y 轴正向走一步。要完成 n 个元素的进栈和出栈利用，最终必要从原点（0,0）走到点（n,n）。但由于合法的进栈出栈序列要求在任何时候出栈次数不超过进栈次数，所以对应的路径不能穿过直线 y=x，只能在直线 y=x 及其下方行走。最终，可得合法的出栈序列数就是卡特兰数的第 n 项：h[n]=h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0], (n≥2, h[0]=h[1]=1)。

【算法代码】

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
long long c[maxn];
int n;
int main() {
cin>>n; //n=1010
c[0]=1,c[1]=1;
for(int i=2; i<=n; i++) {
for(int j=0; j<=i-1; j++) {
c[i]+=c[j]*c[i-j-1];
c[i]%=2020;
}
}
cout<<c[n];
return 0;
}
/*
in:1010
out:1340
*/

复制代码

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/145830268
https://blog.csdn.net/hnjzsyjyj/article/details/145842440
https://blog.csdn.net/hnjzsyjyj/article/details/129148916
https://www.acwing.com/file_system/file/content/whole/index/content/3766019/

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)