大家都知道,斐波那契数列是满足如下性质的一个数列:
• 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)范围内。
感觉自己学的一直是假的矩阵快速幂。。。
辅助矩阵为
\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}
#include<cstdio>
#include<cstring>
#define int long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int MAXN=101;
const int mod=1e9+7;
char buf[1<<20],*p1=buf,*p2=buf;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int n,k;
struct Matrix
{
int m[MAXN][MAXN];
Matrix operator * (const Matrix a)const
{
Matrix ans={};
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans.m[i][j]=(ans.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;
return ans;
}
Matrix pow(int p)
{
Matrix ans,a=(*this);
for(int i=1;i<=n;i++) ans.m[i][i]=1;
while(p)
{
if(p&1) ans=ans*a;
a=a*a;
// a.print();
p>>=1;
}
return ans;
}
void print()
{
for(int i=1;i<=n;i++,puts(""))
for(int j=1;j<=n;j++)
printf("%d ",m[i][j]);
printf("*******************\n");
}
};
main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#endif
k=read();n=2;
Matrix temp,ans;
temp.m[1][1]=0;temp.m[1][2]=1;
temp.m[2][1]=1;temp.m[2][2]=1;
ans.m[1][1]=0;ans.m[1][2]=1;
ans.m[2][1]=0;ans.m[2][2]=1;
temp=temp.pow(k);
ans=ans*temp;
printf("%d",ans.m[1][1]);
return 0;
}