###### tags: `MDCPP題目題解`
# 費波那契湯

**Author : 謝侑哲**

## 題敘

費波那契是個中古時期的義大利數學家，發明了費波那契數列。

至於費波那契數列是甚麼，就是我們常聽到的費氏數列啦!

什麼，還是不知道費氏數列氏什麼，那們下面這串數字總看過了吧

1 1 2 3 5 8 13 21...

費波那契數列就是把前兩個數相加，會變成後一個數

$F(i)+F(i+1) = F(i+2)F(i)+F(i+1)=F(i+2)$
從上面那個式子可以看出

1+1=2, 2+3=5, 3+5=8...

不過今天要來算的不是單純的費波那契數列，而是要來幫助明道食堂的阿姨

明道食堂的阿姨發明了一種湯叫做費波那契湯

湯的原料如下:

今天的湯 = 昨天的湯+前天的湯

不過定期將有衛生食品稽查員到校稽查

為了防止關門大吉，食堂阿姨希望你幫忙算出每天的湯會有多少的黴菌濃度(特殊單位，可能超過一百)

這樣才能夠精準躲過衛生食品稽查員

前兩天的湯黴菌濃度為單位0

不過放了一天，將會各增加單位1的黴菌濃度

因此第三天時，前兩天的黴菌濃度將會變成2,1

第三天的湯黴菌濃度將是2+1=3

第四天時3天的黴菌量將是3,2,4

所以第四天的湯黴菌濃度將是2+4=6

食堂阿姨會向你發出$N$個請求

希望知道第$Q$天的湯黴菌量會是多少


## 輸入說明

第一行的數字$N$為有多少個請求

接下來$N$行數字$Q$為食堂阿姨希望知道的天數

(詢問的天數不超過90)

$0<N<=10^6$
$0<Q<=90$

## 輸出說明

輸出黴菌濃度(可能超過100)

數字可能超過int範圍

## 範例測資

input 1

3
1
2
3

output 1

0
0
3

input 2

4
2
4
6
8

output 2

0
6
21
60

# 題解

#include <bits/stdc++.h>
#define int long long
using namespace std;


const int MAXN = 1e6+50;
int arr[MAXN];

signed main(){

//freopen("4.in","r",stdin);
//freopen("4.out","w",stdout);

int n;
cin>>n;

arr[1]=2;
arr[2]=1;
arr[3]=3;
for(int i=4;i<=100;i++){
    arr[i-1]++;
    arr[i-2]++;
    arr[i] = arr[i-1]+arr[i-2];
}

while(n--){
    int a;
    cin>>a;
    cout<<arr[a]-2<<endl;
}


}