首页 > ACM题库 > HDU-杭电 > HDU 3306-Another kind of Fibonacci-快速幂-[解题报告]HOJ
2014
03-16

HDU 3306-Another kind of Fibonacci-快速幂-[解题报告]HOJ

Another kind of Fibonacci

问题描述 :

As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N – 1) + F(N – 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X * A(N – 1) + Y * A(N – 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)2 +A(1)2+……+A(n)2.

输入:

There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 231 � 1
X : 2<= X <= 231� 1
Y : 2<= Y <= 231 � 1

输出:

There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 231 � 1
X : 2<= X <= 231� 1
Y : 2<= Y <= 231 � 1

样例输入:

2 1 1 
3 2 3 

样例输出:

6
196

#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
typedef struct
{
  int matrix[4][4];
}Matrix;

Matrix multi(Matrix x,Matrix y)
{
  Matrix res;
  int i,j,k;
  int sum;

  for(i = 0;i<4;i++)
    for(j = 0;j<4;j++)
    {
      sum = 0;
      for(k = 0;k<4;k++)
        sum+=(x.matrix[i][k]*y.matrix[k][j])%10007;
      res.matrix[i][j] = sum%10007;
    }
    return res;
}

Matrix powermod(Matrix x,int n)
{
  Matrix res;
  int i,j;

  for(i = 0;i<4;i++)
    for(j = 0;j<4;j++)
    {
       if(i==j)
        res.matrix[i][j] = 1;
       else
        res.matrix[i][j] = 0;
    }
    for(;n;n>>=1)
    {
      if(n&1)
        res = multi(res,x);
       x = multi(x,x);
    }
    return res;
}

int main()
{
    int N,X,Y;
    while(~scanf("%d %d %d",&N,&X,&Y))
    {
        if(N <= 1)
        {
            printf("%d\n",N+1);
            continue;
        }
        X%=10007,Y%=10007;
        Matrix res;
        res.matrix[0][0]=1;
        res.matrix[0][1]=(X*X)%10007;
        res.matrix[0][2]=(Y*Y)%10007;
        res.matrix[0][3]=(2*X*Y)%10007;
        res.matrix[1][0]=0;
        res.matrix[1][1]=(X*X)%10007;
        res.matrix[1][2]=(Y*Y)%10007;
        res.matrix[1][3]=(2*X*Y)%10007;
        res.matrix[2][0]=0;
        res.matrix[2][1]=1;
        res.matrix[2][2]=0;
        res.matrix[2][3]=0;
        res.matrix[3][0]=0;
        res.matrix[3][1]=X;
        res.matrix[3][2]=0;
        res.matrix[3][3]=Y;
        res=powermod(res,N-1);
        printf("%d\n",(2*res.matrix[0][0]+res.matrix[0][1]+res.matrix[0][2]+res.matrix[0][3])%10007);
    }
}

参考:http://blog.csdn.net/alone_l/article/details/19760257


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!