欢迎访问~原文出处——

---

---

题意概括

　　A₀=1,A₁=1,A_N=X*A_N-1+Y*A_N-2(N>=2).求S_N,S_N=A₀²+A₁²+…+A_n².

---

题解

　　这题是用矩阵做的，一看(sou)就知道。

　　设s_i为前i项的答案。

　　如果要求第i项的a_i那么是很简单的。

　　构建矩阵：

　　　　  　a_i-1   　　  a_i

　　a_i-2　 　0 　　　  y

　　a_i-1　 　1 　　　  x

　　但是好像没用。

　　没错，的确没用。

　　我们从二次项考虑：

　　s_i=s_i-1+a_i²

　　    　 =s_i-1+(xa_i-1+ya_i-2)²

　　　　 =s_i-1+x²a_i-1²+y²a_i-2²+2xya_i-1a_i-2

　　那么对于a_k²形式的已经可以完成递推了。但是有一个棘手的东西，就是a_ka_k-1怎么完成递推？

　　我们继续推导：

　　a_ka_k-1=(xa_k-1+ya_k-2)a_k-1

　　　　  =xa_k-1²+ya_k-1a_k-2

　　我们发现a_k-1²和a_k-1a_k-2这两个其实可以按照之前推出来的推，而且不影响后面的。

　　于是，我们可以构建递推矩阵：

　　　　　　　s_i　　   a_i² 　　 a_i-1² 　　　a_ia_i-1

　　s_i-1      　　1 　　   0 　　     0 　　　　 0

　　a_i-1² 　　　x² 　　  x²　　   1 　　　　 x

　　a_i-2²　　　x² 　　  y² 　　   0 　　　　 0

　　a_i-1a_i-2　　2xy 　  2xy 　　  0 　　　　 y

　　

　　意义：

　　s_i  = s_i-1+x²a_i-1²+y²a_i-2²+2xya_i-1a_i-2

　　a_i²=        x²a_i-1²+y²a_i-2²+2xya_i-1a_i-2

　　a_i-1²    =           a_i-1²

　　a_ia_i-1   =         xa_i-1²+                ya_i-1a_i-2

　　

　　那么原始矩阵的第一行就是

　　s₁　　a₁² 　　a₀² 　　a₁a₀

　　算出s_n，就是把这个原始矩阵乘上n-1个递推矩阵。

　　

---

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int mod=10007,m=4;struct Mat{	int v[m][m];	Mat (){}	Mat (int x){		(*this).set(x);	}	void print(){		for (int i=0;i
          
           >=1; } return ans;}int n,x,y;int main(){ while (~scanf("%d%d%d",&n,&x,&y)){ x%=mod,y%=mod; M.set(0); int newi[m]={2,1,1,1}; int newd[m][m]={ {1 ,0 ,0,0}, {x*x%mod ,x*x%mod ,1,x}, {y*y%mod ,y*y%mod ,0,0}, {2*x*y%mod ,2*x*y%mod ,0,y}}; memcpy(M.v[0],newi,sizeof newi); memcpy(Md.v,newd,sizeof newd); Md=MatPow(Md,n-1); M*=Md; printf("%d\n",M.v[0][0]); } return 0;}