题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3306
题目意思：一个斐波那契数列的变式，本来是A[n]=A[n-1]+A[n-2]，现在变成A[n]=N*A[n-1]+Y*A[n-2]。一个很简单的矩阵快速幂。 S(N) = A(0)2 +A(1)2+……+A(n)2对系数矩阵稍微变化一下就可以了。唯一需要注意的是N和Y可能很大，所以需要先mod一下。
思路：首先先求A[n]^2，因为A[n]=N*A[n-1]+Y*A[n-2]，所以A[n]^2=（N*A[n-1]）^2+（Y*A[n-2]）^2=N^2*A[n-1]^2+Y^2*A[n-2]^2+2NY*A[n-1]*A[n-2]。然后我们可以构造矩阵，求前n项和。
|1 0 0 0|
|x*x x*x 1 x|
A= |y*y y*y 0 0|
|2xy 2xy 0 y|
以上为系数矩阵
代码：
1 //Author: xiaowuga 2 #include <bits/stdc++.h> 3 #define maxx INT_MAX 4 #define minn INT_MIN 5 #define inf 0x3f3f3f3f 6 #define size 4 7 #define MOD 10007 8 using namespace std; 9 typedef long long ll; 10 struct Matrix{ 11 ll mat[4][4]; 12 void clear(){ 13 memset(mat,0,sizeof(mat)); 14 } 15 Matrix operator * (const Matrix & m) const{ 16 Matrix tmp; 17 for(int i=0;i<size;i++) 18 for(int j=0;j<size;j++){ 19 tmp.mat[i][j]=0; 20 for(int k=0;k<size;k++){ 21 tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD; 22 tmp.mat[i][j]%=MOD; 23 } 24 } 25 return tmp; 26 } 27 }; 28 Matrix POW(Matrix m,ll k){ 29 Matrix ans; 30 ans.clear(); 31 for(int i=0;i<size;i++) ans.mat[i][i]=1; 32 while(k){ 33 if(k&1) ans=ans*m; 34 k/=2; 35 m=m*m; 36 } 37 return ans; 38 } 39 int main() { 40 ios::sync_with_stdio(false);cin.tie(0); 41 ll n,x,y; 42 while(cin>>n>>x>>y){ 43 Matrix m; 44 m.clear(); 45 m.mat[0][0]=m.mat[3][0]=(x%MOD)*(x%MOD)%MOD; 46 m.mat[0][1]=m.mat[3][1]=(y%MOD)*(y%MOD)%MOD; 47 m.mat[0][2]=m.mat[3][2]=(2*x%MOD)*(y%MOD)%MOD; 48 m.mat[1][0]=m.mat[3][3]=1; 49 m.mat[2][0]=x%MOD;m.mat[2][2]=y%MOD; 50 ll f[4]={1,1,1,2}; 51 Matrix ans=POW(m,n-1); 52 ll sum=0; 53 for(int i=0;i<4;i++){ 54 sum=(sum+ans.mat[3][i]*f[i])%MOD; 55 } 56 cout<<sum<<endl; 57 } 58 return 0; 59 }