Codeforces ECR #188 : G. Grid Path

なるほど。
https://codeforces.com/contest/2204/problem/G

問題

正整数H,Wが与えられる。
H*Wのグリッドにおいて、(1,1)から初めて左・右・下に移動できるとする。
ただしグリッド外に出ることはできない。

通過したことのあるセルの集合としてあり得るのは何通りか。

解法

各行において、通過した左端と右端を状態として持てば、行列累乗に持ち込めるがその場合O(log(H)*W^6)かかりTLEする。
そこで、各左端と右端それぞれのケースを別々に持てば、状態がO(W)個になり、行列累乗がO(log(H)*W^3)で済み間に合う。

const int MAT=301;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};
ll mo;
int N,M;

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	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];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>mo;
	int R=2*M+1;
	Mat A;
	A.v[R-1][R-1]=1;
	
	FOR(x,M) FOR(k,2) {
		for(y=(k==0)?x:0;y<=x; y++) {
			for(i=x;i<M;i++) {
				A.v[R-1][x*2+k]++;
				for(j=y;j<=i;j++) A.v[j*2+(j==y)][x*2+k]++;
			}
		}
		
	}
	
	
	A=powmat(N,A);
	cout<<A.v[R-1][1]<<endl;
	
}

まとめ

こういう数え上げの言い換えは苦手だな…。