Codeforces #329 Div2 E. Strange Calculation and Cats

C,Dで時間をかけすぎたため、本番解法はわかったのに数分間に合わず…。
http://codeforces.com/contest/593/problem/E

問題

H*Wのグリッドがある。
プレイヤーは初期状態で(1,1)にいる。
時刻1ごとに、プレイヤーはその位置にとどまるか隣接マスに移動できる。
ただし時間経過に伴い途中ネコが登場する場合がある。その場合そのマスにいることはできない。

以下のクエリQ個に答えよ。各クエリの時刻は昇順である。

• 時刻tに座標(x,y)に到達するような移動経路の組み合わせ数を答えよ。
• 時刻tに座標(x,y)にネコが登場する。
• 時刻tに座標(x,y)にいたネコが去る。

解法

H*Wは高々20と小さい。
各位置にいる組み合わせ数をベクトルで表現し、時刻１枚の状態遷移を行列で表現して、行列乗算を用いて組み合わせ数を高速に用いていくだけ。
途中クエリにより猫が増減するが、その都度は処理する行列の要素を変えていこう。

int W,H,Q;

ll mo=1000000007;
const int MAT=20;
struct Vec { ll v[MAT]; };
struct Mat { ll v[MAT][MAT]; };
Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) r.v[x][y] += (a.v[x][z]*b.v[z][y]) % mo;
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

Vec mulmatvec(Mat& a,Vec& b,int n=MAT) {
	int x,y,z; Vec r;
	FOR(x,n) r.v[x]=0;
	FOR(x,n) FOR(y,n) (r.v[x] += a.v[x][y]*b.v[y]) %= mo;
	return r;
}
Mat G;
Vec V;

int is[20][20];
int id(int y,int x) { return y*W+x;}
void setup() {
	int y,x;
	ZERO(G.v);
	FOR(y,H) FOR(x,W) if(is[y][x]==0) {
		G.v[id(y,x)][id(y,x)]=1;
		if(y) G.v[id(y,x)][id(y-1,x)]=1;
		if(x) G.v[id(y,x)][id(y,x-1)]=1;
		if(y<H-1) G.v[id(y,x)][id(y+1,x)]=1;
		if(x<W-1) G.v[id(y,x)][id(y,x+1)]=1;
	}
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>Q;
	setup();
	V.v[0]=1;
	
	ll cur=1;
	while(Q--) {
		ll t;
		cin>>i>>y>>x>>t;
		y--; x--;
		auto GG=powmat(t-cur,G,H*W);
		V=mulmatvec(GG,V,H*W);
		if(i==1) {
			cout<<V.v[id(y,x)]<<endl;
		}
		else if(i==2 || i==3) {
			is[y][x]^=1;
			V.v[id(y,x)]=0;
			setup();
			
		}
		cur=t;
	}
}

まとめ

Dよりだいぶ楽でない？
なんでDの方が解いてる人多いんだ。