POJ 3070 Fibonacci——————矩阵快速幂解法

浅浅的花香味﹌ 2022-05-10 11:34 184阅读 0赞

\*\*Fibonacci \*\*  
Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 19481 Accepted: 13467  
**Description**

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 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

.![在这里插入图片描述][3070_1.png]

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 Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0  
9  
999999999  
1000000000  
\-1  
Sample Output

0  
34  
626  
6875  
Hint

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

![.][]

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

![.][. 1]

Source

--------------------

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <cmath>
    #include <map>
    #include <set>
    #include <stack>
    #include <queue>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    
    const int INF = 0x3f3f3f3f;
    const int MAXN = 17;
    const double PI = acos(-1.0);
    const int mod = 10000;
    int N;
    ll b_n = 0;
    ll C[MAXN];
    ll h[MAXN];
    
    struct  matrix{
        	ll m[MAXN][MAXN];};
    
    matrix multi(matrix a,matrix b)//矩阵乘法
    {
        
    	matrix tmp;
    	for(int i=1;i<=N;i++)
    		for(int j=1;j<=N;j++)
    		{
        
    			tmp.m[i][j] = 0;
    			for(int k=1;k<=N;k++)
    				tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k]*b.m[k][j] )%mod;
     		}
     		return tmp;
    
    }
    
    matrix pow_mod(matrix a,int n)//矩阵快速幂
    {
        
    	matrix res;
    	for(int i=1;i<=N;i++)
    		for(int j=1;j<=N;j++)
    			res.m[i][j] = (i==j);
    	while(n)
    	{
        
    		if(n&1)	res = multi(res,a);
    		a = multi(a,a);
    		n>>=1;
    	}
    	return res;
    }
    
    void init(matrix &res,matrix &H)//初始化
    {
        
    	for(int i=1;i<=N;i++)	res.m[1][i]=C[i];//第一列赋值
    	res.m[1][N] = b_n;
    	for(int i=2;i<=N;i++)//构造单位矩阵
    		for(int j=1;j<=N;j++)
    			res.m[i][j] = (i==j+1);
    	res.m[N][N-1] = 0;
    	res.m[N][N] = 1;
    
    	for(int i=1;i<=N;i++)
    	{
        
    		H.m[i][1] = h[N-i];
    		for(int j=2;j<=N;j++)
    			H.m[i][j] = 0;
    	}
    	H.m[N][1]=1;
    }
    
    void slove(int k,int n)
    {
        
    	matrix res,H;
    	init(res,H);
    	res = pow_mod(res,n-k+1);
    	res = multi(res,H);
    	ll ans = res.m[2][1];
    	printf("%lld\n",ans);
    }
    
    
    int main()
    {
        
    	int k,n;
    	k=2;
    	C[1]=1; C[2]=1;
    	h[1]=1; h[2]=1;
    	while(~scanf("%d",&n)&& -1!=n)
    	{
        
    		if(!n)
    		{
        
    			printf("0\n");
    			continue;
    		}
    		N = k+1;
    		slove(k, n);
    	}
    	return 0;
    }

[3070_1.png]: /images/20220510/87cd90df6d29439db5fe24a28509ce74.png
[.]: /images/20220510/1d3d971a4f5249dfbc0dd7acdf65a48d.png
[. 1]: /images/20220510/f5d8c5ed9b2c404a8b52d18f9562d7a2.png