POJ 3070 Fibonacci 矩阵快速幂模板-白红宇

POJ 3070 Fibonacci 矩阵快速幂模板

阅读量：6821 次

发布时间：2019-06-26

本文共 2702 字，大约阅读时间需要 9 分钟。

Fibonacci

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 18607		Accepted: 12920

Description

In the Fibonacci integer sequence, F₀ = 0, F₁ = 1, and F_n = F_n_{− 1} + F_n_{− 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

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

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 F_n. If the last four digits of F_n are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print F_n mod 10000).

Sample Input

099999999991000000000-1

Sample Output

0346266875

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:

Source

题意：求斐波拉契数列，只不过n值很大要用到矩阵快速幂

分析：这是矩阵快速幂的入门题，借此题写下模板。

首先我们很容易的得到递推式：f(n) = f(n-1)+f(n-2)

也很容易的得到他们的矩阵式：

| f(n-1) f(n-2) | x | 1 1 | = | f(n) f(n-1) |

| 0 0 | | 1 0 | | 0 0 |

a b c

写下简单的推导过程：首先把右边式子写在矩阵a第一行，把右边式子可能得到的结果写在矩阵c的第一行，a和c剩下的每行都为0，接下来根据矩阵a和矩阵c写出矩阵b。

得到矩阵式后，就是简单的套用矩阵快速幂的模板了，下面是我的代码

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define debug(a) cout << #a << " " << a << endlusing namespace std;const int maxn = 1e4 + 10;const int mod = 10000;typedef long long ll;struct matrix { ll a[10][10];};matrix base, ans;matrix multip( matrix x, matrix y ) { //求c矩阵的过程 matrix tmp; for( ll i = 0; i < 2; i ++ ) { for( ll j = 0; j < 2; j ++ ) { tmp.a[i][j] = 0; for( ll k = 0; k < 2; k ++ ) { tmp.a[i][j] = ( tmp.a[i][j] + x.a[i][k] * y.a[k][j] ) % mod; } } } return tmp;}ll qow( ll a, ll b ) { //求数的快速幂，与此题无关 ll sum = 1; while( b ) { if( b&1 ) { sum = sum*a%mod; } a = a*a%mod; b /= 2; } return sum;}ll f( ll x ) { //矩阵快速幂的运算 while( x ) { if( x&1 ) { ans = multip( ans, base ); } base = multip( base, base ); x /= 2; } return ans.a[0][0];}int main() { ll n; while( cin >> n ) { if( n == -1 ) { break; } memset( ans.a, 0, sizeof(ans.a) ); //初始化a矩阵和b矩阵，根据你所得到的矩阵式初始化 memset( base.a, 0, sizeof(base.a) ); ans.a[0][0] = 1, ans.a[0][1] = 0; base.a[0][0] = base.a[0][1] = base.a[1][0] = 1; if( n == 0 ) { cout << 0 << endl; } else if( n == 1 ) { cout << 1 << endl; } else { cout << f(n-1) << endl; } } return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9316768.html

你可能感兴趣的文章