# 【題解】ZeroJudge e876: Q1 – 配對連線

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e876
【解題想法】組合數學，卡特蘭數 (Catalan Numbers)

• 卡特蘭數【Wiki
• ans = C (2n, n) / (n+1)
• 測資範圍大：1 ≤ n ≤ 100， 2 ≤ 2n ≤ 200。答案數字很大，要用大數運算。
```#include <iostream>
using namespace std;

int n, a[101][25], tmp[25];

int hold = 0;
for (int i = 0; i < 20; i++){
a[x][i] += tmp[i];
a[x][i] += hold;
hold = a[x][i] / 1000;
a[x][i] %= 1000;
}
}
void mul(int x, int y){
int num;
for (int i = 0; i < 25; i++){
tmp[i] = 0;
}
for (int i = 0; i < 24; i++){
for (int j = 0; j < 24; j++){
num = a[x][i] * a[y][j];
tmp[i+j] += num % 1000;
tmp[i+j+1] += num / 1000;
}
}
for (int i = 0; i < 24; i++){
if (tmp[i] > 1000){
tmp[i+1] += tmp[i] / 1000;
tmp[i] %= 1000;
}
}
}
void print(int x){
bool flag = false;
for (int i = 24; i >= 0; i--){
if (flag){
if (a[x][i] < 100) cout << 0;
if (a[x][i] < 10) cout << 0;
cout << a[x][i];
}
else if (a[x][i] != 0){
flag = true;
cout << a[x][i];
}
}
cout << "\n";
}

int main() {
a[0][0] = 1;
for (int i = 1; i <= 100; i++){
for (int j = 0; j < i; j++){
mul(j, i-1-j);