【題解】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];

void add(int x){
    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);
            add(i);
        }
    }
    while (cin >> n){
        if (n == 0) break;
        print(n);
    }
}
分享本文 Share with friends