网站兼容浏览器,顺德乐从网站建设,环保网站策划书,教做潮男的网站【题目来源】 https://www.luogu.com.cn/problem/P8705 【题目描述】 把 1∼2020 放在 21010 的矩阵里。要求同一行中右边的比左边大#xff0c;同一列中下边的比上边的大。一共有多少种方案? 答案很大#xff0c;你只需要给出方案数除以 2020 的余数即可。 【答案提交】 …【题目来源】 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)/(n1), (n≥2) h[n]C(2n,n)−C(2n,n−1), (n0,1,2,...) h[n]C(2n,n)/(n1), (n0,1,2,...) ● 卡特兰数的第 20 项为 6564120420大于 2×10^9所以代码中要声明为 long long 型。 ● 矩阵填充与进栈出栈过程的对应关系以及和卡特兰数的联系 1第一行填充对应进栈当我们从左到右填充矩阵的第一行时每放入一个数字就相当于一个元素进栈。因为第一行的数字是依次增大的就好像元素依次进入栈中且栈内元素是按照进栈顺序依次排列从小到大。 2第二行填充对应出栈当我们开始填充矩阵的第二行时由于要满足同一列下边的数字比上边大所以放入第二行的数字必须是已经在第一行出现过的数字这就类似于元素出栈。 3可以将进栈push操作看作在平面直角坐标系中向沿 x 轴正向走一步出栈pop操作看作沿 y 轴正向走一步。要完成 n 个元素的进栈和出栈操作最终需要从原点0,0走到点n,n。但由于合法的进栈出栈序列要求在任何时刻出栈次数不超过进栈次数所以对应的路径不能穿过直线 yx只能在直线 yx 及其下方行走。最终可得合法的出栈序列数就是卡特兰数的第 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)。 【算法代码】
#includebits/stdc.h
using namespace std;const int maxn2e55;
long long c[maxn];
int n;int main() {cinn; //n1010c[0]1,c[1]1;for(int i2; in; i) {for(int j0; ji-1; j) {c[i]c[j]*c[i-j-1];c[i]%2020;}}coutc[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/
