2014
03-16

# 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);
}
}

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