hdu 3306 结合本题说下矩阵构造方法

Another kind of FibonacciTime Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 994 Accepted Submission(s): 397


Problem DescriptionInputOutputSample InputSample Output

根据s(n）=s(n-1)+x^2*a(n-1)^+y^2^a(n-2)^2+2xy*a(n-1)*a(n-2) 很容易知道第一行填什么

根据a(n)^2=x^2*a(n-1)^+y^2^a(n-2)^2+2xy*a(n-1)*a(n-2) 也很容易知道第二行填什么

第三行更简单

第四行 不好直接找出来 这时候就要充分利用题目所给条件了

把后者分开 即a(n)*a(n-1)=(X * A(N - 1) + Y * A(N - 2))*a(n-1)

=x*a(n-1)^2+y*a(n-2)*a(n-1) 这时候很容易就能看出来矩阵应该是什么 了

矩阵构造完毕 我以前不知道如何去构造矩阵 煞是头疼啊，我想这种矩阵构造方法应该是可以的 没有人教我 只能 自己参考了一些资料 不知道有没有更简单快速的方法 求大神教授

AC代码

#include<stdio.h>#define N 4#define mod 10007struct mat{int mar[4][4];};mat a,b,c,init,temp;mat res=  {  1,0,0,0,          0,1,0,0,          0,0,1,0,          0,0,0,1  };mat mul(mat a1,mat b1)  {      int i,j,l;      mat c1;      for (i=0;i<N;i++)      {          for (j=0;j<N;j++)          {              c1.mar[i][j]=0;              for (l=0;l<N;l++)              {                  c1.mar[i][j]+=(a1.mar[i][l]*b1.mar[l][j])%mod;                  c1.mar[i][j]%=mod;              }          }      }      return c1;  }  mat er_fun(mat e,int x){mat tp;tp=e;e=res;while(x){if(x&1)e=mul(e,tp);tp=mul(tp,tp);x>>=1;}return e;}int main(){      int n,x,y,i,j;  while(scanf("%d %d %d",&n,&x,&y)!=EOF)  {  x=x%mod; y=y%mod;             init.mar[0][0]=1; init.mar[0][1]=(x*x)%mod; init.mar[0][2]=(y*y)%mod; init.mar[0][3]=(2*x*y)%mod;             init.mar[1][0]=0; init.mar[1][1]=(x*x)%mod; init.mar[1][2]=(y*y)%mod; init.mar[1][3]=(2*x*y)%mod; init.mar[2][0]=0; init.mar[2][1]=1; init.mar[2][2]=0; init.mar[2][3]=0; init.mar[3][0]=0; init.mar[3][1]=x; init.mar[3][2]=0; init.mar[3][3]=y; a=init;             b=er_fun(a,n-1); printf("%d\n",(2*b.mar[0][0]+b.mar[0][1]+b.mar[0][2]+b.mar[0][3])%mod);               }return 0;}

hnust_xiehonghao