题目地址：HDU 3306
没什么智商的题目，只要把构造矩阵硬算出来就行。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; const int mod =1e4+7; struct matrix { int ma[5][5]; }init, res; matrix Mult(matrix x, matrix y) { matrix tmp; int i, j, k; for(i=0;i<4;i++) { for(j=0;j<4;j++) { tmp.ma[i][j]=0; for(k=0;k<4;k++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp; } matrix Pow(matrix x, int k) { matrix tmp; int i, j; for(i=0;i<4;i++) for(j=0;j<4;j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } int main() { int k, x, y, i, j; while(scanf("%d%d%d",&k,&x,&y)!=EOF) { x%=mod; y%=mod; memset(init.ma,0,sizeof(init.ma)); init.ma[0][0]=init.ma[3][0]=(x*x)%mod; init.ma[0][1]=init.ma[3][1]=(y*y)%mod; init.ma[0][2]=init.ma[3][2]=(2*x*y)%mod; init.ma[1][0]=1; init.ma[2][0]=x; init.ma[2][2]=y; init.ma[3][3]=1; res=Pow(init,k-1); int ans; ans=(res.ma[3][0]+res.ma[3][1]+res.ma[3][2]+res.ma[3][3]*2)%mod; /*for(i=0;i<4;i++) { printf("%d ",res.ma[3][i]); }*/ printf("%d\n",ans); } return 0; }