【POJ3070】斐波那契数列f[n]的后四位,n达1e+9(矩阵快速幂模版题)
题目地址:https://vjudge.net/problem/POJ-3070
题意:
斐波那契数列0 1 1....f[i]=f[i-1]+f[i-2],给定n(0 ≤ n ≤ 1,000,000,000)),求f[n]的后四位。
解题思路:
普通的数组肯定存不下了,这个时候就要用到矩阵快速幂了。
以下截图来自博客https://blog.csdn.net/zhangxiaoduoduo/article/details/81807338
ac代码:
#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
#define maxn 1005
typedef long long ll;
const ll inf=1e+18;
using namespace std;
ll a1[4][4]={0},t[4][4]={0},res[4][4]={0};//f[n]=res[1][1]
void multi(ll a[][4],ll b[][4])
{
ll temp[5][5]={0};
for(ll i=1;i<=2;i++)
{
for(ll j=1;j<=2;j++)
{
for(ll k=1;k<=2;k++)
{
temp[i][j]+=(a[i][k]*b[k][j])%10000;
}
}
}
for(ll i=1;i<=2;i++)
for(ll j=1;j<=2;j++)
a[i][j]=temp[i][j];
}
void pow(ll n)//t^(n-1)
{
memset(res,0,sizeof(res));
for(int i=1;i<=2;i++)
res[i][i]=1;//单位矩阵,存t^(n-1)的结果
while(n)//将快速幂换成矩阵快速幂
{
if(n&1)
multi(res,t);
multi(t,t);
n>>=1;
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
ll n;
while(scanf("%lld",&n)==1&&n!=-1)
{
if(n==0)
{
printf("0\n");
continue;
}
a1[1][1] = 1,a1[1][2]=0, a1[2][1] = 0,a1[2][2]=0;//初始矩阵
t[1][1] = 1, t[1][2] = 1, t[2][1] = 1, t[2][2] = 0;//转移矩阵初始化
pow(n-1);
multi(res,a1);//res存t^(n-1)*a1的结果
printf("%lld\n",res[1][1]);
}
return 0;
}