洛谷P1962 斐波那契数列【矩阵运算】
题目背景
大家都知道,斐波那契数列是满足如下性质的一个数列:
• f(1) = 1
• f(2) = 1
• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
题目描述
请你求出 f(n) mod 1000000007 的值。
输入格式:
·第 1 行:一个整数 n
输出格式:
第 1 行: f(n) mod 1000000007 的值
输入样例1
5
输出样例1
5
输入样例2
10
输出样例2
55
说明
对于 60% 的数据: n ≤ 92
对于 100% 的数据: n在long long(INT64)范围内。
题解分析:
这题主要的难点就在超大的数据范围
” n在long long(INT64)范围内。”
直接递推什么的肯定是不行的
所以这时候我们的矩阵运算就派上用场啦
我们依次将斐波那契数放入矩阵
[f(1)f(2)](1)
[f(2)f(3)](2)
[f(3)f(4)](3)
一号矩阵是已知的
那么要怎样推出后面的矩阵呢
我们试着用1矩阵乘以下面这个矩阵A
[0111](A)
发现是不是得到了二号矩阵
再用二号矩阵去乘A矩阵
是不是得到了三号?
(真的是妙啊~妙啊~)
由此不难找出规律
f(n)第一次出现的地方
就是算出A^(n-2)再乘以原斐波那契初始矩阵
最后要求的f(n)一定在答案矩阵的最下面的位置
所以总结起来
矩阵运算的题目
就是像这样找出一个初始矩阵
然后便可以运用该矩阵进行优化运算
规律应该很清楚了吧
代码里就不写什么注释了
(就是懒 = =)
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
ll read()
{
ll f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}
void print(ll x)
{
if(x<0){putchar('-');x=-x;}
if(x>9)print(x/10);
putchar(x%10+'0');
}
const ll mod=1000000007;
ll n;
struct node
{
ll a[5][5];
node()
{
for(ll i=1;i<=2;i++)
for(ll j=1;j<=2;j++)
a[i][j]=0;
}//初始化矩阵
}d,fibo;
ll res[10][10];
node quick_pow(node f,ll k)
{
if(k==1) return f;
else if(k%2==1)
{
node temp=quick_pow(f,k-1);
node ans;
for(ll i=1;i<=2;i++)
for(ll j=1;j<=2;j++)
for(ll k=1;k<=2;k++)
ans.a[i][j]+=(f.a[i][k]*temp.a[k][j])%mod,ans.a[i][j]%=mod;
return ans;
}
else if(k%2==0)
{
node temp=quick_pow(f,k/2);
node ans;
for(ll i=1;i<=2;i++)
for(ll j=1;j<=2;j++)
for(ll k=1;k<=2;k++)
ans.a[i][j]+=(temp.a[i][k]*temp.a[k][j])%mod,ans.a[i][j]%=mod;
return ans;
}
}
int main()
{
n=read();
if(n==1||n==2){print(1);return 0;}
//记得特判
fibo.a[1][1]=1; fibo.a[2][1]=1;
d.a[1][1]=0; d.a[1][2]=1;
d.a[2][1]=1; d.a[2][2]=1;
//运算用的矩阵
ll k=n-2;
node temp=quick_pow(d,k);
//先计算A矩阵的n-2次幂
for(ll i=1;i<=2;i++)
for(ll j=1;j<=1;j++)
for(ll k=1;k<=2;k++)
res[i][j]+=(temp.a[i][k]*fibo.a[k][j])%mod,res[i][j]%=mod;
//与f(1)与f(2)的矩阵相乘得出最后答案矩阵
print(res[2][1]);
return 0;
}