Another kind of Fibonacci

**Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2353    Accepted Submission(s): 936
**

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

2 1 1

3 2 3

Sample Output

6

196

 思路：矩阵快速幂；

S(n) = ∑f(n)2 = S(n-1)+f(n)2 = S(n-1)+x2f(n-1)2+y2f(n-2)2+2xyf(n-1)f(n-2)；

然后f(n)*f(n-1) = (x*f(n-1)+y*f(n-2))*f(n-1) = x*f(n-1)2+y*f(n-1)*f(n-2)；

然后构造矩阵；

其中的第三个矩阵写错了，应该是s[n-1];     f[n-1]^2;     f[n-2]^2;  f[n-1]*f[n-2];

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include