题目链接:https://vjudge.net/problem/UVA-12470

题目意思:我们都知道斐波那契数列F[i]=F[i-1]+F[i-2],现在我们要算这样的一个式子T[i]=T[i-1]+T[i-2]+T[i-3]的第n想是多少,很套路的矩阵快速幂,入门题,算是熟悉矩阵快速幂的操作吧。

代码:

 //Author: xiaowuga
#include<bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
#define N 3
using namespace std;
const int MOD=;
typedef long long ll;
ll n,size=;//第n项,矩阵大小
struct Matrix{
ll mat[N][N];
void clear(){
memset(mat,,sizeof(mat));
}
Matrix operator * (const Matrix & m) const{
Matrix tmp;
int i ,j,k;
tmp.clear();
for( i=;i<size;i++)
for( k=;k<size;k++){
if(mat[i][k]==) continue;
for( j=;j<size;j++){
tmp.mat[i][j]+=mat[i][k]*m.mat[k][j];
tmp.mat[i][j]%=MOD;
}
}
return tmp;
}
};
Matrix POW(Matrix m,ll k){
Matrix ans;
memset(ans.mat,,sizeof(ans.mat));
for(int i=;i<size;i++) ans.mat[i][i]=;
while(k){
if(k&) ans=ans*m;
k=k>>;
m=m*m;
}
return ans;
}
int main() {
Matrix m;
m.clear();
m.mat[][]=m.mat[][]=m.mat[][]=;
m.mat[][]=;m.mat[][]=;
ll f[]={,,};
while(cin>>n&&n){
if(n<=) {cout<<n-<<endl; continue;}
Matrix ans=POW(m,n-);
ll sum=;
for(int i=;i<;i++){
sum+=ans.mat[][i]*f[i]%MOD;
sum%=MOD;
}
cout<<sum<<endl;
}
return ;
}
05-11 15:24
查看更多