好久没有写矩阵了，写挂了好几次QAQ。几乎所有的坑都跳了一遍……
题目大意：给定一个$n imes n$的矩阵，坐标为$(x,y)$的格子的权值为$x+y$。一个人初始在$(sx,sy)$处，初始速度为$(dx,dy)$，他下一秒能到达的地方为$((x+dx-1)mod n+1,(y+dy-1)mod n+1)$。当人到达一个地方$(x,y)$时，他的速度将会变为$(dx+x+y,dy+x+y)$。每秒钟所有格子内的权值都会加$1$。问$t$秒后人所在的位置。
正解：矩阵快速幂。
设$sx(i)$表示第$i$秒时人所在格子的横坐标，$sy(i)$表示所在格子的纵坐标；$dx(i)$表示第$i$秒时人的横向速度，$dy(i)$表示第$i$秒时的纵向速度。根据题意有：
$dx(t)=dx(t-1)+sx(t-1)+sy(t-1)+t-1$
$dy(t)=dy(t-1)+sx(t-1)+sy(t-1)+t-1$
（别忘了每秒钟格子的权值会加$1$）
同时根据题意有：
$sx(t)=sx(t-1)+dx(t)$
$sy(t)=sy(t-1)+dy(t)$
考虑取余操作，这使得$mod n$后的值只可能在$[0,n-1]$中。所以我们不妨平移人，将人的位置分别往上，往左移动一格。这样坐标就变为了$(sx-1,sy-1)$。但这样会导致速度比原来的速度少$2$，所以要在原来的式子中加上$2$。这样我们有：
$dx(t)=dx(t-1)+sx(t-1)+sy(t-1)+t-1+2$
$dy(t)=dy(t-1)+sx(t-1)+sy(t-1)+t-1+2$
将$dx(t),dy(t)$代入$sx(t),sy(t)$中，得到：
$sx(t)=2 imes sx(t-1)+dx(t-1)+sy(t-1)+t+1$
$sy(t)=2 imes sy(t-1)+dy(t-1)+sx(t-1)+t+1$
考虑构造转移矩阵，我们有：
$egin{bmatrix} sx(t-1) \ sy(t-1)\dx(t-1)\dy(t-1)\t-1\1 end{bmatrix}$ $ imes$ $egin{bmatrix} 2&1&1&0&1&2 \ 1&2&0&1&1&2\1&1&1&0&1&2\1&1&0&1&1&2\0&0&0&0&1&1\0&0&0&0&0&0end{bmatrix}$ $=$ $egin{bmatrix} sx(t) \ sy(t)\dx(t)\dy(t)\t\1 end{bmatrix}$
矩阵快速幂处理即可。时间复杂度$O(216log_2t)$。
代码：
#include<cstdio> #include<iostream> #include<cstring> #define int long long using namespace std; int n,sx,sy,dx,dy,t,y[10],p; struct node { int a[10][10]; node(){ memset(a,0,sizeof(a)); } inline void build(){ for (int i=1;i<=6;i++) a[i][i]=1; } }x; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void init() { x.a[1][1]=2;x.a[1][2]=1;x.a[1][3]=1;x.a[1][4]=0;x.a[1][5]=1;x.a[1][6]=2; x.a[2][1]=1;x.a[2][2]=2;x.a[2][3]=0;x.a[2][4]=1;x.a[2][5]=1;x.a[2][6]=2; x.a[3][1]=1;x.a[3][2]=1;x.a[3][3]=1;x.a[3][4]=0;x.a[3][5]=1;x.a[3][6]=2; x.a[4][1]=1;x.a[4][2]=1;x.a[4][3]=0;x.a[4][4]=1;x.a[4][5]=1;x.a[4][6]=2; x.a[5][1]=0;x.a[5][2]=0;x.a[5][3]=0;x.a[5][4]=0;x.a[5][5]=1;x.a[5][6]=1; x.a[6][1]=0;x.a[6][2]=0;x.a[6][3]=0;x.a[6][4]=0;x.a[6][5]=0;x.a[6][6]=1; y[1]=sx-1;y[2]=sy-1;y[3]=dx;y[4]=dy;y[5]=0;y[6]=1; } node operator * (const node x,const node y) { node z; for (int i=1;i<=6;i++) for (int j=1;j<=6;j++) for (int k=1;k<=6;k++) z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%p+p)%p; return z; } signed main() { //freopen("data.in","r",stdin); //freopen("ans.out","w",stdout); n=read(),sx=read(),sy=read(),dx=read(),dy=read(),t=read();p=n; if (t==0) { printf("%lld %lld",sx,sy); return 0; } init(); node ans;ans.build(); while(t) { if (t&1) ans=ans*x; x=x*x; t>>=1; } int tx=0,ty=0; for(int i=1;i<=6;i++) tx=(tx+y[i]*ans.a[1][i]%p+p)%p, ty=(ty+y[i]*ans.a[2][i]%p+p)%p; printf("%lld %lld",tx+1,ty+1); return 0; }