hdu 3306 Another kind of Fibonacci

ここをクリックするとhdu 3306が転送されます

                            **Another kind of Fibonacci**
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2005    Accepted Submission(s): 787

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

nとx、y、f(n)=x*f(n-1)+y*f(n-2);そしてs(n)=f(0)^2+f(1)^2+....+f(n)^2を求めます.問題を解く構想:やはり行列乗算の余剰;直接コード:

/* 2015 - 8 - 14    Author: ITAK            。。。。            ，           ，             ，       。 */

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 4;
const int mod = 10007;
typedef long long LL;
typedef struct
{
    LL  m[maxn][maxn];
}Matrix;
Matrix P = {1,1,0,0,
            0,0,0,0,
            0,0,0,0,
            0,1,0,0
           };
Matrix I = {1,0,0,0,
            0,1,0,0,
            0,0,1,0,
            0,0,0,1
           };
Matrix matrix_mul(Matrix a, Matrix b)
{
    int i, j, k;
    Matrix c;
    for(i=0; i<maxn; i++)
    {
        for(j=0; j<maxn; j++)
        {
            c.m[i][j] = 0;
            for(k=0; k<maxn; k++)
                c.m[i][j] += (a.m[i][k] * b.m[k][j]) % mod;
            c.m[i][j] %= mod;
        }
    }
    return c;
}

Matrix quick_mod(LL m)
{
    Matrix ans = I, b = P;
    while(m)
    {
        if(m & 1)
            ans = matrix_mul(ans, b);
        m >>= 1;
        b = matrix_mul(b, b);
    }
    return ans;
}
int main()
{
    LL n, x, y;
    while(~scanf("%lld%lld%lld",&n,&x,&y))
    {
        Matrix tmp;
        x %= mod;
        y %= mod;
        P.m[1][1] = (x*x) % mod;
        P.m[1][2] = (2*x*y) % mod;
        P.m[1][3] = (y*y) % mod;
        P.m[2][1] = x;
        P.m[2][2] = y;
        tmp = quick_mod(n);
        LL ans = (tmp.m[0][0]+tmp.m[0][1]+tmp.m[0][2]+tmp.m[0][3])%mod;
        cout<<ans<<endl;
    }
    return 0;
}