Another kind of Fibonacci
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2258 Accepted Submission(s): 900
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 <= 231 – 1
X : 2<= X <= 231– 1
Y : 2<= Y <= 231 – 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
Sample Output
Author
wyb
Source
Recommend
wxl
已知下列初始条件和递推式，求S(N)。
由于S(N)计算需要用到A(N)^2，计算A(N)^2，发现需要A(N-1)*A(N-2)的值，
而A(N-1)*A(N-2)可以由A(N-2)、A(N-3)运算得到。
又有，
将以上式子列成矩阵
得到下面含幂次式子，以便使用快速幂优化计算过程，
使用矩阵乘法和矩阵快速幂实现程序，注意取模。
HDU 3306 Another kind of Fibonacci
原文：http://www.cnblogs.com/cumulonimbus/p/5691035.html
