題目連結：
題目大意：
第一列給定一正整數 t （1 ≦ t ≦ 10000），代表有 t 筆測試資料，每筆佔一列。每列給定 n 、 k （2 ≦ n ≦ 30 ， 1≦ k ≦ 2 ^ 50），代表求 n-Fibonacci （推廣的費氏數列）的第 k 項的值為何？將該值求除以 1000000007 的餘數後輸出。
n-Fibonacci 定義為，該數列的前 n 項皆為 1 。對於該數列的第 i 項為第 i - 1 項 + 第 i - 2 項 + …… + 第 i - n 項，即第 i - 1 項 ～ 第 i - n 項的總和。而 n ＝ 2 時即是我們熟悉的、原本的費氏數列。
範例輸入：
5
2 5
3 2
10 12
25 1000
30 1125899906842624
範例輸出：
5
1
19
637354692
966611599
解題思維：
首先看看原本的費氏數列的矩陣快速冪解法，請參見很久以前有提及該解法的文章。
那麼推廣上述的式子，該矩陣的內容會長怎樣呢？也就是我們要找到一個 n × n 的矩陣 A ，其滿足：
對原本費氏數列的矩陣之觀察，可以看到矩陣 A 的形式應為：
也就是第一列第二行為 1 、 第二列第三行為 1 …… 第 i 列第 i + 1 行為 1 ，然後最後一列的數字全為 1 ，其他地方皆為 0 。
因此，求出 A ^ (k - 1) ，即可套入下式得出所求的第 k 項：
而 A ^ (k - 1) 可以由矩陣快速冪快速地得出。
但是 n-Fibonacci 矩陣快速冪解法之時間複雜度為
n ^ 3 × log k
而暴力一項一項地求解的時間複雜度為
kn
（可以到 n + k，利用類似前綴和（Prefix Sums）的概念）
因此，對於大的 n 值，但 k 值小的情況而言，使用矩陣快速冪反而更慢。反而照原生的解法更快。
而本題的第一組測試資料即是大量的小 k 值之測資。所以光使用矩陣快速冪會直接快樂地超時。可以設定一個 k 的上界，超過該上界使用矩陣快速冪，以下則使用普通的解法求解。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
