首页 > 代码库 > 快速求斐波那契数列（矩阵乘法+快速幂）
快速求斐波那契数列（矩阵乘法+快速幂）
斐波那契数列
给你一个n；f(n)=f(n-1)+f(n-2)
请求出 f(f(n))，由于结果很大请
对答案 mod 10^9+7;
1<=n<=10^100;
用矩阵乘法+快速幂求斐波那契数列是经典应用；
矩阵公式 C i j=C i k *C k j;
根据递推式 构造2*2矩阵；
原始矩阵
1 0
0 1
矩阵 2
1 1
1 0
原始矩阵与矩阵 2相乘达到转化状态效果；
对矩阵二进行快速幂 乘法；达到快速转化矩阵的效果；
即使达到快速转化状态；那么大的数据范围也很难求解；
高精？这有一种不用高精的方法；
打个暴力 求循环节；
即 f(f(n))%mod同余f(f(n%k)%p)%mod;
暴力求k p 即可;
k=6e9+6；p=2e9+2；
以下暴力程序
#include<cstdio>
typedef long long LL;
LL f[100005],k;
int main(){
f[1]=1;k=1;
while (1){
k++;
f[2]=(f[1]+f[0])%1000000007;
if (f[2]==2) {
printf("%lld\n",k);
}
f[0]=f[1];
f[1]=f[2];
}
}
AC 程序
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define mod 1000000007
#define ll long long
int T,i,j,k;
ll n;
ll a[2][2],b[2][2],c[2][2],f[2][2];
char ch;
void Mod(ll mo)
{
n=0;
ll q=getchar();
while(q<48||q>57)q=getchar();
while(q>=48&q<=57)
{
n=(n*10+q-48)%mo;
q=getchar();
}
}
void mul(ll a[2][2],ll b[2][2],ll mo)
{
ll c[2][2]={0};
for(i=0;i<2;++i)
for(j=0;j<2;++j)
for(k=0;k<2;++k)
c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mo)%mo;
for(i=0;i<2;++i)
for(j=0;j<2;++j)
a[i][j]=c[i][j];
}
int main()
{
// freopen("xx.in","r",stdin);
// freopen("xx.out","w",stdout);
scanf("%d\n",&T);
for(;T--;)
{
Mod(mod*6ll+6);
if(n<=2)
{
if(!n)printf("0\n");
else printf("1\n");
continue;
}
n-=1;
a[0][0]=a[0][1]=a[1][0]=1;a[1][1]=0;
f[0][0]=f[1][1]=1;f[1][0]=f[0][1]=0;
while(n)
{
if(n&1)mul(f,a,mod*2ll+2);
mul(a,a,mod*2ll+2);
n>>=1;
}
n=f[0][0]-1;
a[0][0]=a[0][1]=a[1][0]=1;a[1][1]=0;
f[0][0]=f[1][1]=1;f[1][0]=f[0][1]=0;
while(n)
{
if(n&1)mul(f,a,mod);
mul(a,a,mod);
n>>=1;
}
printf("%d\n",f[0][0]);
}
}
【
问题描述】
令??(??)为斐波那契数列第??项，其中??(0) = 0,??(1) = 1,??(??) = ??(??? 1) +??(?? ?2)。所以要干啥呢？求??(??(??))。【输入格式】第一行一个整数??代表数据组数。接下来??行每行一个整数??。【输出格式】??行每行一个整数代表答案对10 9 + 7取模的值。【样例输入】40126【样例输出】01121【样例解释】无。【数据规模与约定】215 490。70%的数据，1 ≤ ?? ≤ 10 5 。对于100%的数据，1 ≤ ?? ≤ 10 3 ,1 ≤ ?? ≤ 10 100 。
快速求斐波那契数列（矩阵乘法+快速幂）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。