Codeforces #226 Div2. E. Bear in the Field

アプローチはそこそこの速度で思いついたけど、本番バグがとりきれなかった。
http://codeforces.com/contest/385/problem/E

問題

(1,1)～(N,N)で表現されるNxNのグリッドがある。
プレイヤーの初期位置をSX,SY、初期速度をDX,DY、実行時間をTとする。

プレイヤーは時間Tに到達するまで以下の処理を繰り返す。

• 今の位置を(X,Y)、時間をTとするなら、速度をX,Y座標両方向ともに(X+Y+T)加える。
• 今の位置からDX,DYだけ移動する。グリッドの周囲はループしている。
• 時刻を1加えて先頭に戻る。

時間T経過後、プレイヤーはどの位置に停止するか答えよ。

解法

時刻Tの状態を位置(X,Y)、速度(VX,VY)とする。
次の時刻では、まず速度が(VX+(X+Y+T),VY+(X+Y+T))となり、次に位置が(2X+Y+VX+T, X+2Y+VY+T)となる。
よって、この遷移を6x6の行列で表現し、T乗すればよい。Tに1加えるため、位置２次元・速度２次元・時刻・定数の6要素で構成する。

グリッドの形状より、mod処理後の数値が0～(N-1)ではなく1～Nとなる点に注意。
本番この部分がうまく処理できずpretest通らなかった。

答えは下記の式で求められる。

int N;
ll SX,SY,DX,DY,T;
ll mat[6][6];
ll mat2[6][6];

const int MAT=6;
ll mo;
void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=0;
	FOR(i,n) r[i][i]=1;
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) {
				h[x][y]=0;
				FOR(z,n) h[x][y] += r[x][z]*a2[z][y];
				h[x][y] = 1+(h[x][y]+mo-1)%mo;
			}
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y];
		}
		FOR(x,n) FOR(y,n) {
			h[x][y]=0;
			FOR(z,n) h[x][y] += a2[x][z]*a2[z][y];
			h[x][y] = 1+(h[x][y]+mo-1)%mo;
		}
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y];
		p>>=1;
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>SX>>SY>>DX>>DY>>T;
	mo=N;
	if(DX<0) DX+=N;
	if(DY<0) DY+=N;
	
	mat[0][0]=2;
	mat[0][1]=mat[0][2]=mat[0][4]=1;
	mat[1][1]=2;
	mat[1][0]=mat[1][3]=mat[1][4]=1;
	mat[2][0]=mat[2][1]=mat[2][2]=mat[2][4]=1;
	mat[3][0]=mat[3][1]=mat[3][3]=mat[3][4]=1;
	mat[4][4]=mat[4][5]=1;
	mat[5][5]=1;
	
	powmat(T,6,mat,mat2);
	
	ll lx=SX*mat2[0][0]+SY*mat2[0][1]+DX*mat2[0][2]+DY*mat2[0][3]+mat2[0][5];
	ll ly=SX*mat2[1][0]+SY*mat2[1][1]+DX*mat2[1][2]+DY*mat2[1][3]+mat2[1][5];
	_P("%lld %lld\n",1+(lx+mo-1)%mo,1+(ly+mo-1)%mo);
}

まとめ

アプローチはあってたんだし、本番に解ききりたかったなぁ。