---
title: 1B 巴斯卡三角形
tags: solution
---

---
# B. 巴斯卡三角形

稍微觀察一下，不難會發現此題與原本的巴斯卡三角形的規律：

以及本題設計的數量級偏小，所以可以直接使用我們高中所學的二項式定理來解，

倒置的巴斯卡三角形於第 x 排第 y 個數的分母值會是：$\text{ }x\times\dbinom{x-1}{y-1}$

### Preliminary Version :
> Time Complexity : $O(T\cdot (x+y+(x-y)))$

# include <iostream>
using namespace std;

long long f(long long n){    // factorial
    long long result = 1;

    while(n)
        result *= n--;

    return result;
}

int main(){
    long long T,n,m;

    cin>>T;
    while(T--){
        cin>>n>>m;
        --m, --n;
        cout<<"1/"<<(n+1)*(f(n)/f(m)/f(n-m))<<'\n';
    }
}

---

### More Better Version :
可以將各項階乘的數字先計算完，然後用陣列存起來，這樣就不用每次計算時都要計算階乘。
這個步驟通常會稱為 **建表(Building Table)**

> Time Complexity : $O(T)$

# include <iostream>
using namespace std;

int main(){
    int T,n,m;
    long long f[21];  // factorial, f[n] = n!

    // building factorial table
    f[0] = 1;         // 0! = 1
    for(n = 1 ; n<21 ; n++)
        f[n] = f[n-1]*n;

    cin>>T;
    while(T--){
        cin>>n>>m;
        --m, --n;
        cout<<"1/"<<(n+1)*(f[n]/f[m]/f[n-m])<<'\n';
    }
}

---

但若數量級提升到更大的數字範圍時，像是想要詢問第10000排第5000個數字時，還有辦法解嗎？
可以稍微想想看有沒有可以不用二項式定理的解法。