[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;
	}
	qPow(n-m);
	lld ans = 0;
	for(lld i=0;i<m;i++){
		ans += aas[i][0]%mmdd;
		ans %= mmdd;
	}
	printf("%lld",ans);
	return 0;
}

void qPow(lld p){
	bool flag=0;
	lld m2[110][110];
	for(lld i=0;i<m;i++){
		for(int j=0;j<m;j++){
			aas[i][j] = (i==j);
		}
	}
	while(p){
		if(p&1){
			auto tp = new long long [110][110];
			matrixTimes(aas,(!flag)?m1:m2,tp);
			std::swap(tp,aas);
		}
		p>>=1;
		if(!flag)
			matrixTimes(m1,m1,m2);
		else
			matrixTimes(m2,m2,m1);
		flag = !flag;
	}
}
void matrixTimes(lld a[][110], lld b[][110], lld c[][110]){
	for(lld i = 0;i<m;i++){
		for(lld j = 0;j<m;j++){
			c[i][j] = 0;
			for(lld k = 0;k<m;k++){
				c[i][j] += (a[i][k]*b[k][j])%mmdd;
				c[i][j] %= mmdd;
			}
		}
	}
}