矩阵的快速取幂法——求类Fibonacci数列（2）

╰+攻爆jí腚メ 2022-07-15 08:30 146阅读 0赞

POJ 3070   Fibonacci

Time Limit:  1000MS  Memory Limit:  65536K  Total Submissions:  3817 Accepted:  2688

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn ? 1 \+ Fn ? 2 forn ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is

.![Center][]

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number ?1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fnare all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

099999999991000000000-1

Sample Output

0346266875

#include<iostream>
    #include<cstring>
    using namespace std;
    int sq[35][2][2]={ { {1,1}, {1,0} } };
    int main()
    { 
        int n,ans,i,j,k,l; 
        int m[2][2]={0}; 
        for(l=1;l<32;l++) 
            for(i=0;i<2;i++) 
                for(j=0;j<2;j++) 
                    for(k=0;k<2;k++) 
                        sq[l][i][j]=(sq[l][i][j]+sq[l-1][i][k]*sq[l-1][k][j])%10000; 
        while(cin>>n&&n!=-1) 
        { 
            if(n==0) 
            {
                cout<<0<<endl;
                continue;
            } 
            if(n==1||n==2) 
            {
                cout<<1<<endl;
                continue;
            } 
            int t[2][2]={
       {1,0},{0,1}}; 
            n=n-1;
            l=0; 
            while(n) 
            { 
                if(n&1) 
                { 
                    memset(m,0,sizeof(m)); 
                    for(i=0;i<2;i++) 
                        for(j=0;j<2;j++) 
                            for(k=0;k<2;k++) 
                                m[i][j]=(m[i][j]+t[i][k]*sq[l][k][j])%10000; 
                    for(i=0;i<3;i++) 
                        for(j=0;j<3;j++) 
                            t[i][j]=m[i][j]; 
                } 
                l++; 
                n=n>>1; 
            } 
            ans=t[0][0]%10000; 
            cout<<ans<<endl; 
        } 
        return 0;
    }

[Center]: /images/20220715/1d8aa5e8d7cc4df399a45aa9283c2677.png