Fibonacci(Poj 3070)

2020-01-26 378次阅读 0条评论 1人点赞

这一专题应该是矩阵快速幂，有几道没在HDOJ上找到原题，它应该是直接提交到POJ上去的

Problem 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

.

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

My Code

#include 
#include 

using namespace std;
struct Matrix
{
    int M[5][5];
};
Matrix mul(Matrix m1, Matrix m2, int n)
{
    Matrix m3;
    memset(m3.M,0,sizeof(m3.M));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                m3.M[i][j] = (m3.M[i][j] + (m1.M[i][k] % 10000) * (m2.M[k][j] % 10000)) % 10000;
    return m3;
}
Matrix pow(Matrix m, int n)     //矩阵快速幂
{
    Matrix ans;
    ans.M[0][0] = 1;            //单位矩阵，相当于数字1
    ans.M[1][1] = 1;
    ans.M[1][0] = 0;
    ans.M[0][1] = 0;
    while (n)
    {
        if (n & 1)              //就是把普通的快速幂中的普通乘法换成矩阵的乘法
            ans = mul(ans, m, 2);
        m = mul(m, m, 2);
        n >>= 1;
    }
    return ans;
}
int main()
{
    int n;
    Matrix m;
    m.M[0][0] = 1;
    m.M[1][0] = 1;
    m.M[0][1] = 1;
    m.M[1][1] = 0;
    while (cin >> n && n != -1)
        cout << pow(m, n).M[1][0] % 10000 << endl;
    return 0;
}