Codeforces 385(#226 Div2 only) E. Bear in the Field

問題

nxnのグリッドがあって、最初(sx, sy)にいる。
最初の速度は(dx, dy)で、速度(dx, dy)で移動すると、
x' = (x + dx - 1) mod n + 1
y' = (y + dy - 1) mod n + 1に移動する。

移動の前に、今いるグリッドを(x, y)とすると、dx, dyがともに(今のターン数) + x + yずつ増える。
tターン繰り返した後の位置を求めよ。

制約条件

n≦10^9
t≦10^18
座標は1-origin

方針

(x, y, dx, dy, t)から次のターンの状態を表してみると、
x' = x + (x + y + t) + dx
y' = y + (x + y + t) + dy
dx'= dx + x + y + t
dy'= dy + x + y + t
t' = t + 1

なので、この移動は行列で表せて、
行列の繰り返し二乗法を使えば、tターン後の状態がO(log t)で求まる。

ソースコード

int mod;
typedef vector<vi> M;
inline M operator*(const M & a, const M &b){
	M c(a.size(), vi(b[0].size()));
	rep(i, c.size()) rep(j, c[0].size()){
		ll s = 0;
		rep(k, a[0].size()) s += (ll)a[i][k] * b[k][j] % mod;
		c[i][j] = s % mod;
		if(c[i][j] == 0) c[i][j] = mod;
	}
	return c;
}
inline M pow(M a, ll m){
	M res(a.size(), vi(a.size()));
	rep(i, a.size()) res[i][i] = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * a;
		a = a * a;
	}
	return res;
}
int main(){
	
	M A(6, vi(6));
	
	int a[6][6] ={
		{2, 1, 1, 0, 1, 0},
		{1, 2, 0, 1, 1, 0},
		{1, 1, 1, 0, 1, 0},
		{1, 1, 0, 1, 1, 0},
		{0, 0, 0, 0, 1, 1},
		{0, 0, 0, 0, 0, 1}
	};
	rep(i, 6) rep(j, 6) A[i][j] = a[i][j];
	
	ll sx, sy, dx, dy, t;
	M b(6, vi(1));
	cin >> mod >> sx >> sy >> dx >> dy >> t;
	
	b[0][0] = sx; b[1][0] = sy; b[2][0] = dx; b[3][0] = dy; b[4][0] = 0; b[5][0] = 1;
	rep(i, 6) b[i][0] = (b[i][0] % mod + mod) % mod;
	
	b = pow(A, t) * b;
	cout << b[0][0] << " " << b[1][0] <<endl;
	
	return 0;
}