题目地址：HDU 4686
我去。。因为忘记把函数里的k定义成64位的，导致TLE了一晚上。。。晕。。
这题没什么技巧，就是根据公式构造就行。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 const LL mod=1e9+7; struct matrix { LL ma[8][8]; } init, res; matrix Mult(matrix x, matrix y) { int i, j, k; matrix tmp; memset(tmp.ma,0,sizeof(tmp.ma)); for(i=0; i<7; i++) { for(k=0; k<7; k++) { for(j=0; j<7; j++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp; } matrix Pow(matrix x, LL k) { matrix tmp; int i, j; for(i=0; i<7; i++) for(j=0; j<7; 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() { LL k, ax, ay, bx, by, i, j, a0, b0; while(scanf("%I64d",&k)!=EOF) { scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a0,&ax,&ay,&b0,&bx,&by); if(k==0) { puts("0"); continue ; } memset(init.ma,0,sizeof(init.ma)); init.ma[0][0]=ax; init.ma[0][4]=1; init.ma[1][1]=bx; init.ma[1][5]=1; init.ma[2][0]=(ax*by)%mod;init.ma[2][1]=(ay*bx)%mod;init.ma[2][2]=(ax*bx)%mod;init.ma[2][3]=1; init.ma[3][3]=1; init.ma[4][4]=1; init.ma[5][5]=1; init.ma[6][0]=(ax*by)%mod;init.ma[6][1]=(ay*bx)%mod;init.ma[6][2]=(ax*bx)%mod;init.ma[6][3]=1;init.ma[6][6]=1; res=Pow(init,k-1); LL ans; ans=(a0*res.ma[6][0]+b0*res.ma[6][1]+a0*b0%mod*res.ma[6][2]+ay*by%mod*res.ma[6][3]+ay*res.ma[6][4]+by*res.ma[6][5]+a0*b0%mod*res.ma[6][6])%mod; printf("%I64d\n",ans); } return 0; }