【題目來源】
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=1010c[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/
?