题目链接

题意：

有一只熊，初始在(sx,sy)处，如果当前的位置在(x,y)，那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+1)处， dx[i] = k[i-1] + dx[i-1],dy[i]=k[i-1] + dy[i-1]，k表示的是某个点的花丛数目。

初始点(x,y)的花丛数为x+y,每经过一个时间，所有点的花丛数增加1.

所以，k[i] = x[i] + y[i] + i-1，现在问经过时间t后，熊的位置在哪里。也就是x[t],y[t]的值。

思路：

我们不妨先只考虑x方向的，因为y方向完全相同。

观察x[t]的式子， x[t] = (x[t-1] + dx[t-1] -1) % n +1。。这个%n之后+1简直蛋疼得一逼。。。

我们不妨构造_g[t] = x[t]-1_，这样原式子就变成了 _g[t] = (g[t-1] + dx[t-1]) %n _...看起来爽了很多。。。

观察式子_g[t] = (g[t-1] + dx[t-1]) % n_，我们发现这是一个前缀和的形式。

根据在hdu4686解题报告  中提到的经验，对于求和的式子，我们只需要考虑每一项的构造法。

因此问题转化成构造矩阵dx[t]

dx[t] = k[t-1] + dx[t-1]

其中_k[t] = x[t] + y[t] + t-1,_我们写成gx[t]和gy[t]的形式

有**k[t] = gx[t] + gy[t] + t + 1**

而_k[t-1] = gx[t-1] + gy[t-1] + t_

因此可以得到k[t-1]与k[t]之间的递推关系:** k[t] = k[t-1] + dx[t-1] + dy[t-1] + 1**

观察到k[t]的表达式中同时包含dx,dy项，因此之前考虑的单独处理x和y的想法应该是行不通的。我们考虑同事处理x,y。