hdu3306--Another kind of Fibonacci（矩阵快速幂）

 2 1 1 
3 2 3 

 6
196 

Sn = S(n-1) + An^2 =  S(n-1) + X^2A*(n-1)^2 + 2*X*Y*A(n-1)*A(n-2) + Y^2*A(n-2)^2

也就得到Sn由S(n-1) , A(n-1) , A(n-2) , A(n-1)*A(n-2)得到，由此可以转化为矩阵相乘

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
#define MOD 10007
struct node
{
    LL a[5][5] ;
    int n ;
};
node mul(node p,node q)
{
    int i , j , k ;
    node s ;
    for(i = 0 , s.n = p.n ; i < p.n ; i++)
        for(j = 0 ; j < p.n ; j++)
        {
            s.a[i][j] = 0 ;
            for(k = 0 ; k < p.n ; k++)
                s.a[i][j] = ( s.a[i][j] + p.a[i][k] * q.a[k][j] ) % MOD ;
        }
    return s ;
}
node pow(node p,int k)
{
    if( k == 1 )
        return p ;
    node s = pow( p,k/2 ) ;
    s = mul(s,s) ;
    if( k%2 )
        s = mul(s,p) ;
    return s ;
}
int main()
{
    LL n , x , y , i , j , ans ;
    node p , s ;
    while( scanf("%I64d %I64d %I64d", &n, &x, &y) != EOF )
    {
        p.n = 4 ;
        memset(p.a,0,sizeof(p.a)) ;
        p.a[0][0] = 1 ;
        p.a[1][0] = p.a[1][1] = (x*x) % MOD ;
        p.a[2][0] = p.a[2][1] = (2*x*y) % MOD ;
        p.a[3][0] = p.a[3][1] = (y*y) % MOD ;
        p.a[1][2] = x % MOD ;
        p.a[2][2] = y % MOD ;
        p.a[1][3] = 1 ;
        s = pow(p,n-1) ;
        ans = s.a[0][0] * 2 ;
        for(i = 1 ; i < 4 ; i++)
            ans = ( ans + s.a[i][0] ) % MOD ;
        printf("%I64d\n", ans) ;
    }
    return 0;
}

hdu3306--Another kind of Fibonacci（矩阵快速幂）

原文：http://blog.csdn.net/winddreams/article/details/42806021