TopCoderOpen 2021 Round1B : Hard Antiqueen

これは出ておけばレート増ではあったが。
https://community.topcoder.com/stat?c=problem_statement&pm=16964&rd=18645

問題

R*Cのチェス盤を考える。
チェスの駒Antiqueenを、Queenとは真逆、すなわちQueenで1手で到達できないところに1手で移動できる駒とする。
任意の場所にこの駒を置き、N回(この駒の移動可能先へ)移動することを繰り返す。
この駒の移動経路は何通りあるか求めよ。

解法

ひたすら累積和を使う問題。
n回目の移動を行う際、(n-1)回目までの移動後に各マスにいる場合の数について：

• 盤面全体
• 縦方向
• 横方向
• 斜め方向(左上から右下と、左下から右上双方)

の累積和を計算しておくと、これらの加減算でn回目の移動後に駒が各マスにいる場合の数を計算できる。
計算量はO(RCN)。

const ll mo=1000000007;


class Antiqueen {
	public:
	int countPaths(int R, int C, int N) {
		ll from[202][202]={};
		int y,x;
		FOR(y,R) FOR(x,C) from[y][x]=1;
		while(N--) {
			ll LR[202]={};
			ll UD[202]={};
			ll RD[402]={};
			ll RU[402]={};
			ll S=0;
			FOR(y,R) FOR(x,C) {
				(S+=from[y][x])%=mo;
				(LR[y]+=from[y][x])%=mo;
				(UD[x]+=from[y][x])%=mo;
				(RD[y-x+200]+=from[y][x])%=mo;
				(RU[y+x]+=from[y][x])%=mo;
			}
			FOR(y,R) FOR(x,C) {
				from[y][x]=(S-LR[y]-UD[x]-RD[y-x+200]-RU[y+x]+3*from[y][x]+4*mo)%mo;
			}
		}
		
		ll ret=0;
		FOR(y,R) FOR(x,C) ret+=from[y][x];
		return ret%mo;
		
		
	}
}

まとめ

RCN、一時お世話になってました。