POJ3070Fibonacci（矩阵快速幂）

小咪咪 2021-10-25 12:22 344阅读 0赞

在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)

。

给定整数n，求Fibnmod10000

。  
输入格式

输入包含多组测试用例。

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

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

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

每个结果占一行。  
数据范围

0≤n≤2∗109

输入样例：

0  
9  
999999999  
1000000000  
\-1

输出样例：

0  
34  
626  
6875

分析：  
矩阵快速幂的入门题了。  
已知f3 = f2 + f1；  
所以，我们想得到第n项的时候，要保存第n-1和第n-2项的值。  
F（n，n-1）= F1（n-1，n-2）\* X；  
X为一个矩阵。观察等式可以得到，F的第一项由F1的第一二项的和得到。  
F的第二项，就是F1的第一项。  
故X可定义为第一行1 1 第二行1 0

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    ll Graph[3][3];
    ll result[3][3];
    ll n;
    const ll mod = 10000;
    
    void Graph_Mul(ll a[][3],ll b[][3])
    {
       ll result[3][3];
       result[1][1] = a[1][1] * b[1][1] % mod + a[1][2] * b[2][1] % mod;
       result[1][2] = a[1][1] * b[1][2] % mod + a[1][2] * b[2][2] % mod;
       result[2][1] = a[2][1] * b[1][1] % mod+ a[2][2] * b[2][1] % mod;
       result[2][2] = a[2][1] * b[1][2] % mod + a[2][2] * b[2][2] % mod;
       result[1][1] %= mod; result[1][2] %= mod;
       result[2][1] %= mod; result[2][2] %= mod;
       a[1][1] = result[1][1]; a[1][2] = result[1][2];
       a[2][1] = result[2][1]; a[2][2] = result[2][2];
    }
    
    void Multi_Graph(ll n)
    {
        while(n)
        {
            if(n & 1)
            {
                Graph_Mul(result,Graph);
            }
            n >>= 1;
            Graph_Mul(Graph,Graph);
        }
    }
    
    int main()
    {
        Graph[1][1] = 1; Graph[1][2] = 1;
        Graph[2][1] = 1; Graph[2][2] = 0;
    
        while(~scanf("%lld",&n))
        {
            if(n == -1) break;
            if(n == 0){ printf("0\n"); continue;}
            else if(n == 1) {printf("1\n"); continue;}
            else if(n == 2) {printf("1\n"); continue;}
    
            Graph[1][1] = 1; Graph[1][2] = 1;
            result[1][1] = 1; result[1][2] = 1;
            Graph[2][1] = 1; Graph[2][2] = 0;
            result[2][1] = 1; result[2][2] = 0;
            Multi_Graph(n - 3);
            printf("%lld\n",(result[1][1] + result[2][1]) % mod);
        }
    }