首页 > ACM题库 > HDU-杭电 > HDU 2855-Fibonacci Check-up-快速幂-[解题报告]HOJ
2014
02-17

HDU 2855-Fibonacci Check-up-快速幂-[解题报告]HOJ

Fibonacci Check-up

问题描述 :

Every ALPC has his own alpc-number just like alpc12, alpc55, alpc62 etc.
As more and more fresh man join us. How to number them? And how to avoid their alpc-number conflicted?
Of course, we can number them one by one, but that’s too bored! So ALPCs use another method called Fibonacci Check-up in spite of collision.

First you should multiply all digit of your studying number to get a number n (maybe huge).
Then use Fibonacci Check-up!
Fibonacci sequence is well-known to everyone. People define Fibonacci sequence as follows: F(0) = 0, F(1) = 1. F(n) = F(n-1) + F(n-2), n>=2. It’s easy for us to calculate F(n) mod m.
But in this method we make the problem has more challenge. We calculate the formula , is the combination number. The answer mod m (the total number of alpc team members) is just your alpc-number.

输入:

First line is the testcase T.
Following T lines, each line is two integers n, m ( 0<= n <= 10^9, 1 <= m <= 30000 )

输出:

First line is the testcase T.
Following T lines, each line is two integers n, m ( 0<= n <= 10^9, 1 <= m <= 30000 )

样例输入:

2
1 30000
2 30000

样例输出:

1
3

点击打开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;
}

解题参考:http://blog.csdn.net/chenguolinblog/article/details/10629907


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。