[IOJ] 14. 費氏數列問題
題目連結: https://ioj.infor.org/problems/14 由題目可看出這是一個標準的線性遞迴，而居然是線性遞迴的話，那都可以用矩陣乘法搭配快速冪來讓時間複雜度降到$O(m^3 \log_2{(n-m)})$，然後不難發現其要用的$1 \times m$橫矩陣是$\left( \begin{array}{clr} 1 & 1 & \cdots & 1 \end{array} \right)$，而$m \times m$正方形矩陣則是$\left( \begin{array}{clr} k_{1} & 1 & 0 & 0 & \cdots \\ k_{2} & 0 & 1 & 0 & \cdots \\ k_{3} & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ k_{m} & 0 & 0 & 0 & \cdots \end{array} \right)$至於會溢位的部分則按照題敘，每次在做加法乘法之類的時候都模一次$10^9+7$，因為可以證明先算再模跟先模再算再模都會得到相同的結果的。 #include <stdio.h>
#include <algorithm>
typedef long long lld;
const lld mmdd = 1000000007;
lld m1[110][110]={0};
auto aas = new lld [110][110];
lld n,m;
void qPow(lld);
void matrixTimes(lld[][110],lld[][110],lld[][110]);
int main(){
scanf("%lld %lld",&n,&m);
for(lld i=0;i<m;i++){
scanf("%lld",&m1[i][0]);
if(i+1<m)
m1[i][i+1] = 1;...