hdu 2855 Fibonacci Check-up

点击打开hdu 2855

思路: 递推+矩阵快速幂

分析:

1 题目的意思是给定n和m，要求

2 这一题有两种思路，对于这种的题肯定是有递推式的，那么找不到递推式的时候我们尝试去打表

   下面我打出了前几十项，发现了n >= 2的时候有f(n) = 3*f(n-1)-f(n-2)，那么我们可以利用矩阵快速幂求f(n)

3 另一种思路是考虑f(n) = f(n-1) + f(n-2)，那么我们可以利用矩阵求出任意的f(n)

   1 1 *  f(n-1) = f(n)

   1 0    f(n-2)    f(n-1)

   那么对于n >= 2的时候，我们假设左边的矩阵为A，那么A^(n-1)即可求出答案

   那么A^(n-1)为 f(n) f(n-1)

                          f(n-1) f(n-2)

   那么根据我们知道二项式定理为(a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)*b+C(n,2)a^(n-2)*b^2+...+C(n,n)b^n

   那么我们发现所求的式子和上面很像，因为f(n)可以利用上面的A矩阵的n-1次方求出

   那么原式所求变成(1+A)^n，这里的1为单位矩阵。因为做了n次方，那么最终的答案就是ans.mat[0][1] 或ans.mat[1][0]

代码:

// 方法一
/************************************************
 * By: chenguolin                               *
 * Date: 2013-08-30                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2;

int n , MOD;
struct Matrix{
    int mat[N][N];
    Matrix operator*(const Matrix &m)const{
        Matrix tmp;
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                tmp.mat[i][j] = 0;
                for(int k = 0 ; k < N ; k++)
                    tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
                tmp.mat[i][j] %= MOD;
            }
        }
        return tmp;
    }
};

int Pow(Matrix m){
    if(n <= 1) return n%MOD;
    Matrix ans;
    ans.mat[0][0] = ans.mat[1][1] = 1;
    ans.mat[0][1] = ans.mat[1][0] = 0;
    n--;
    while(n){
        if(n&1)
            ans = ans*m;
        n >>= 1;
        m = m*m;
    }
    return (ans.mat[0][0]%MOD+MOD)%MOD;
}

int main(){
    Matrix m;
    m.mat[0][0] = 3 ; m.mat[0][1] = -1;
    m.mat[1][0] = 1 ; m.mat[1][1] = 0;
    int cas;
    scanf("%d" , &cas);
    while(cas--){
         scanf("%d%d" , &n , &MOD);
         printf("%d\n" , Pow(m));
    }
    return 0;
}

/************************************************
 * By: chenguolin                               *
 * Date: 2013-08-30                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2;

int n , MOD;
struct Matrix{
    int mat[N][N];
    Matrix operator*(const Matrix &m)const{
        Matrix tmp;
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                tmp.mat[i][j] = 0;
                for(int k = 0 ; k < N ; k++)
                    tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
                tmp.mat[i][j] %= MOD;
            }
        }
        return tmp;
    }
};

int Pow(Matrix m){
    if(n <= 1) return n%MOD;
    Matrix ans;
    ans.mat[0][0] = ans.mat[1][1] = 1;
    ans.mat[0][1] = ans.mat[1][0] = 0;
    while(n){
        if(n&1)
            ans = ans*m;
        n >>= 1;
        m = m*m;
    }
    return ans.mat[1][0]%MOD;
}

int main(){
    Matrix m;
    m.mat[0][0] = 2 ; m.mat[0][1] = 1;
    m.mat[1][0] = 1 ; m.mat[1][1] = 1;
    int cas;
    scanf("%d" , &cas);
    while(cas--){
        scanf("%d%d" , &n , &MOD);
        printf("%d\n" , Pow(m));
    }
    return 0;
}