題目連結：
題目大意：
輸入第一列給定一正整數 t（1 ≦ t ≦ 100000），代表有 t 筆測試資料，每筆佔一列。每列給定一正整數 n（1 ≦ n ≦ 200000），代表有一條道路上被分成 n 個格子。每個格子一開始都是白色的，而我們可以選擇某些格子（至少一個，不能不選）塗成黑色的，但是不能有兩個連續的黑色格子。試問總共會有多少道路格子塗色的方式？由於方法數可能很大，因此請取除以 998244353 的餘數作為輸出值。
範例輸入：
範例輸入 #1
1
2
範例輸入 #2
1
3
範例輸入 #3
1
10
範例輸出：
範例輸出 #1
2
範例輸出 #2
4
範例輸出 #3
143
解題思維：
假設沒有一定要至少選一個格子塗成黑色。則我們可以看到其方法數遞迴式將與費氏數列相似：
令 D'[i] 為在可以不塗色的情況下有 i 個格子時的塗色方法，而
D'[i] = D'[i - 1] + D'[i - 2]
第一項是因為我們可以選擇不塗第 i 格，因此可以只看前 i - 1 格的塗法；而第二項則是因為可以選擇塗第 i 格，而此時第 i - 1 格不能塗色，所以看前 i - 2 格可以怎麼塗。且已知
D'[1] = 2 、 D'[2] = 3
接著令 D[i] 為真正的所求，即必定要塗至少一個格子的方法數。而此時完全不塗色只會固定佔一個方法數，故
D[i] = D'[i] - 1
因此可以推得
D[i] = D[i - 1] + D[i - 2] + 1
且
D[1] = 1 、 D[2] = 2
接著就預先建表，之後對於每個輸入的 n 值輸出對應的方法數即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
