HDU 3117 Fibonacci Numbers(矩阵)

Fibonacci Numbers

【题目类型】矩阵

&题解：

后4位是矩阵快速幂求,前4位是用log加Fibonacci通项公式求,详见上一篇博客

&代码：

#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn= 2 +9;
int a[90]={0};
struct Mat
{
    ll m[maxn][maxn];
};
int n=2,x,M=1e8,M2=1e4;
Mat Mul(Mat A,Mat B)
{
    Mat C;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        C.m[i][j]=0;
        for(int k=0;k<n;k++){
            C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j])%M;
        }
    }
    return C;
}
Mat bPow(Mat A,ll k)
{
    Mat B;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            B.m[i][j]=(i==j);
        }
    }
    while(k){
        if(k&1)
            B=Mul(B,A);
        A=Mul(A,A);
        k>>=1;
    }
    return B;
}
Mat A;
int main()
{
	freopen("E:1.txt","r",stdin);
	while(cin>>x){
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            A.m[i][j]=1;
        A.m[1][1]=0;
        if(x==0)
            puts("0");
        else if(x==1)
            puts("1");
        else{
            A=bPow(A,x-1);
            if(x<40)
            cout<<A.m[0][0]%M<<endl;
            else {
                double u1=log10(1/sqrt(5)),u2=log10((1+sqrt(5))/2);
                double t=u1+x*u2;
                t=t-(int)t;
                cout<<(int)(pow(10,t)*1000);
                printf("...%04d
",A.m[0][0]%M2);
            }

        }
	}
	return 0;
}