AtCoder ARC #202 : B - Japanese "Knight's Tour"

これはすんなりだった。
https://atcoder.jp/contests/arc202/tasks/arc202_b

問題

トーラス状になっているH*Wの将棋盤がある。
あるマスにある桂馬の駒をH*W回動かしたとき、全部のマスを1回ずつ通って元のマスに戻るような移動方法は何通りか。

解法

Hが偶数の時は解なし。
桂馬は1手で2つ上の行に移動するが、1つ上の行に移動すると考えてもよい。

桂馬は縦方向にW周することになるが、その際同じ行にいる桂馬は、毎回左右同じ方向に移動しないと、異なるマスを通るようにできない。
よって、結局考えるべき組み合わせは各行において左右どちらに移動するかの2^H通りだけである。
また、縦に1周する際に横に何マスずれるかを考えると、ずれる数がwの時、GCD(abs(w),W)=1なら、W周する間に全部のマスを通ることができる。

あとはwを総当たりしながら、左右の移動パターンを二項係数で足し合わせていこう。

int H,W;
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	if(H%2==0) {
		cout<<0<<endl;
		return;
	}
	
	ll ret=0;
	if(W%2) {
		FOR(i,H+1) {
			j=abs(H-2*i);
			if(__gcd(j,W)==1) {
				ret+=comb(H,i);
			}
		}
	}
	else {
		FOR(i,2*H+1) {
			j=abs(2*H-2*i);
			if(__gcd(j/2,W/2)==1) {
				ret+=comb(2*H,i);
			}
		}
	}
	cout<<ret%mo<<endl;
}

まとめ

Aよりすんなりだった。