矩阵快速幂
如果n较小的话,我们可以直接使用递推式$O(n)$处理.
但这道题的n规模很大,达到了2e9,故线性递推一定会超时.
至此,我们需要一种更快的处理方法.
这时,就需要使用矩阵快速幂.
先将斐波拉契数列的第一和第二项放在一个数组(将其看作一个12的矩阵).
然后我们需要根据斐波拉契数列的递推式和矩阵乘法的规则构造一个矩阵.
让之前的12的矩阵子在和构造出的矩阵进行n次矩阵乘法后,就可以得到斐波拉契数列的第n项.
再结合快速幂的思想递推求解即可.
时间复杂度 $O(忘了)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e4;
inline void mul(int f[2],int a[2][2])
{
int c[2];
memset(c,0,sizeof(c));
for(int j=0;j<2;j++)//矩阵乘法
for(int k=0;k<2;k++)
c[j]=(c[j]+(long long)f[k]*a[k][j])%mod;//记得一定要开long long
memcpy(f,c,sizeof(c));
}
inline void selfmul(int a[2][2])
{
int c[2][2];
memset(c,0,sizeof(c));
for(int k=0;k<2;k++)//矩阵乘法
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
c[i][j]=(c[i][j]+(long long)a[i][k]*a[k][j])%mod;//记得一定要开long long
memcpy(a,c,sizeof(c));
}
int main()
{
while(1){
int n;
int f[2]={1,1},a[2][2]={{0,1},{1,1}};//f数组为斐波拉契数列的第一和第二项,a数组为构造的矩阵
scanf("%d",&n);
if(!n){//特判第0项
printf("0\n");
continue;
}
if(n==-1)
break;
n--;
while(n){//矩阵快速幂
if(n&1)
mul(f,a);
selfmul(a);
n>>=1;
}
printf("%d\n",f[0]);
}
return 0;
}