[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$,因為可以證明先算再模跟先模再算再模都會得到相同的結果的。
由題目可看出這是一個標準的線性遞迴,而居然是線性遞迴的話,那都可以用矩陣乘法搭配快速冪來讓時間複雜度降到$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;
}
}
}
}
留言
張貼留言