Another kind of Fibonacci
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1526 Accepted Submission(s): 583
Problem Description 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.
Input There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 2
31 ? 1
X : 2<= X <= 2
31? 1
Y : 2<= Y <= 2
31 ? 1
Output For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.
Sample Input
2 1 1
3 2 3
Sample Output
6
196
Author wyb
Source HDOJ Monthly Contest ? 2010.02.06
题解及代码：
#include
#include
#include
using namespace std; const int mod=10007; struct mat { __int64 t[4][4]; void set() { memset(t,0,sizeof(t)); } } a,b; mat multiple(mat a,mat b,__int64 n,int p) { int i,j,k; mat temp; temp.set(); for(i=0; i
>=1; b=multiple(b,b,n,p); } return t; } void init(__int64 x,__int64 y) { b.set(); b.t[0][0]=1; b.t[1][0]=x*x%mod;b.t[1][1]=x*x%mod;b.t[1][2]=x;b.t[1][3]=1; b.t[2][0]=2*x*y%mod;b.t[2][1]=2*x*y%mod;b.t[2][2]=y; b.t[3][0]=y*y%mod;b.t[3][1]=y*y%mod; } int main() { __int64 n,x,y; while(cin>>n>>x>>y) { x=x%mod; y=y%mod; init(x,y); a=quick_mod(b,4,n-1,mod); cout<<(2*a.t[0][0]+a.t[1][0]+a.t[2][0]+a.t[3][0])%mod<