题目描述

在斐波那契数列中，$Fib_0=0, Fib_1=1, Fib_n=Fib_{n-1}+Fib_{n-2} (n>1)$。

给定整数n，求$Fib_n mod 10000$。

输入格式
输入包含多组测试用例。

每个测试用例占一行，包含一个整数n。

当输入用例n=-1时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围
$0≤n≤2∗10^9$

样例

输入样例：
0
9
999999999
1000000000
-1
输出样例：
0
34
626
6875

矩阵乘法

如果这道题目N不大的话,那么上面的题目描述已经告诉你递推$O(n)$做法了,但是现在N范围很大,我们必须使用一种速度极快的算法,加速我们的时间效率.

一般来说遇到这种递推的题目,或者说变化形式是一种线性递推的运算,我们就可以初步判断这道题目是矩阵乘法了.

我们可以设一个1*2的矩阵$F(n)=[Fib_{n-1},Fib_n]$,然后我们的目标就是要通过这个矩阵去推出$Fib_n$

那么我们可以这样设计$F(n)=F(n-1)*A$其中A为我们设计的转移状态矩阵,那么现在我们思考一下,怎么设计出这样的矩阵A呢?并且我们不仅要保存$Fib_n$还要保存$Fib_{n-1}$为下一次$Fib_{n+1}$做好准备.

其实不难,我们可以令A矩阵为$\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}$,换行符被吞掉了.

这是什么意思呢?其实第一行意思是$Fib_{n-1}*0+Fib_n$,第二行意思则是$Fib_{n-1} \times 1+Fib_n \times 1$

然后我们最后再用快速幂快速计算,达到优化速度.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int K=10000;
int n;
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]+f[k]*a[k][j])%K;
    memcpy(f,c,sizeof(c));
}
void mulself(int a[2][2])
{
    int c[2][2];
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%K;
    memcpy(a,c,sizeof(c));
}
int power(int b,int c)
{
    int f[2]={0,1};
    int a[2][2]={{0,1},{1,1}};
    while(b)
    {
        if (b&1)
            mul(f,a);
        mulself(a);
        b>>=1;
    }
    cout<<f[0]<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    while(cin>>n && n!=-1)
        power(n,K);
    return 0;
}

作者：秦淮岸灯火阑珊
链接：https://www.acwing.com/activity/content/code/content/24642/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。