AtCoder ARC #046 : D - うさぎとマス目

面白かったです。
http://arc046.contest.atcoder.jp/tasks/arc046_d

問題

H*Wの2次元グリッドがある。
初期状態で一番左上のセルに兎がいる。
兎は各マスで右か下の隣接マスに移動できる。（ただし、右端・下端からさらに右・下に移動しようとすると左端・上端にワープ出来る）

各マスを1回ずつたどり、最後の初期位置に戻りたい。
そのような移動経路が何通りあるか求めよ。

解法

Editorialを見て回答。

あるマスは1回ずつしか通らないので、上か左のどちらかからしか来ることはできない。
よって各マスについて上と左のマスは同じ向きに移動することになる。
言い換えると、各マスとその左下のマスは同じ向きに移動する。

そう考えると、ほとんどのマス同士は同じ向きに移動することになる。
実質移動経路の取り方は最初のd=GCD(H,W)手を決めると、後はそのd手を繰り返すこととなる。

最初のd手で、(0,0)から(y,x)に移動したとする(y+x=d)。
この(+y,+x)のマスへの移動を繰り返すことで、全部の(d手ごとの移動で到達可能な)マスを通りたい。
(+y,+x)の移動について、縦方向の周期はH/GCD(H,y)、横方向の周期はW/(W,x)である。よって合わせて全体の周期はLCM(H/GCD(H,y),W/(W,x))となる。
この周期が、全マスのうちd手ごとに通るマスの集合H*W/dと一致するなら、そのような(+y,+x)の移動経路は条件を満たす。
また、そのような最初のd手の選び方はComb(d,x)通りである。

まとめると以下のようになる。

• d = GCD(H,W)を求める。
• x+y = dとなる非負整数x,yを総当たりし、LCM(H/GCD(H,y),W/(W,x))==H*W/dとなるx,yがあればComb(d,x)を答えに加算する。

ll H,W;
ll mo=1000000007;
ll ret;

ll combi(ll N_, ll C_) {
	const int NUM_=1000001;
	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; string s;
	
	cin>>H>>W;
	
	ll d=__gcd(H,W);
	ll x,y;
	for(y=1;y<d;y++) {
		x=d-y;
		ll a=H/__gcd(H,y);
		ll b=W/__gcd(W,x);
		if(a*b/__gcd(a,b)==H*W/d) ret +=combi(d,x);
	}
	cout<<ret%mo<<endl;
	
}

まとめ

気が付くとコードは非常にあっさりなのがいいね。