yukicoder : No.834 Random Walk Trip

これこんなシンプルに解けるのか…。
https://yukicoder.me/problems/no/834

問題

1～Nの番号のマス目が順に並んでおり、初期状態で1番のマスにコマを置くとする。
以下の手順をM回繰り返す。

• コインを投げて表が出た場合、1つ番号の小さいマスにコマを動かす。ただしすでに1番の場合は動かさない。
• 裏が出た場合、1つ番号の大きいマスにコマを動かす。ただしすでにN番の場合は動かさない。

最後コマが1番のマスに戻るケースについて、M回コインを投げたのちのコマのマス目番号を並べかたは何通りか。

解法

マス目が1～Nではなく、[1～N]の後に[N～1]が逆順で連結したうえで、先頭と末尾が連結した2N個のリング状に並んだマス目があるとする。
元の問題では1番またはN番のマスにおいてコマが動かないケースがあったので面倒だったが、この2N個のマス目では、コマは必ず両隣のどちらかに移動するうえ、移動先の番号は元の問題の条件と一致する。

よって後者の条件で解けばよい。
これだとだいぶ楽で、2*N個のマス目がリング状に並んでいて、M回コマを右または左に動かしたとき、(右の移動回数-左の移動回数) % 2Nが0か(2N-1)となるケースを列挙すればよく、これは二項係数の和で求められる。

int N,M;
ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	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>>N>>M;
	if(N==1) return _P("1\n");
	
	ll ret=0;
	for(i=-M;i<=M;i++) if((i&1)==(M&1)) {
		x=(i%(2*N)+2*N)%(2*N);
		if(x==0 || x==2*N-1) ret+=comb(M,(M+i)/2);
	}
	cout<<ret%mo<<endl;
	
	
}

まとめ

このテクは覚えておきたい。