Bubble Cup 8 Final : H. Bots

問題文の理解に手間取った。
http://codeforces.com/contest/575/problem/H

問題

だいぶ意訳する。
整数Nが与えられる。
青と赤を順にいくつか選んでいく。青も赤も選んだ回数がN個以下になる選び方は何通りありか。

解法

元の問題文だと赤青の辺の遷移だが、ここでは青い玉と赤い玉を順に並べることを考える。

青玉の数Bを総当たりする場合を考える。
青玉と、あとこれ以降は選ばないとみなす仮の玉を考える。これら(B+1)個の玉の前後に赤い玉N個を分けるので、全体ではとなる。

また、以下のように考えると組み合わせ１個で解ける。
青い玉N個の後に1個「これ以降の玉は無視するとみなす」という特殊な玉を加えた(N+1)個の玉を考える。
同様に、赤い玉N個の前に1個「これ以前の玉は無視するとみなす」という特殊な玉を加えた(N+1)個の玉を考える。

(N+1)個の玉の列２つを混ぜ、２つの特殊な玉に挟まれたものを抜き出すと、題意を満たす弾の並びを一意に重複なく選べる。
これは単純な組み合わせでで解ける。
ただし、特殊な玉が隣接する２ケースは、実際の赤玉青玉の並びは同じになり二重カウントされてしまうので、1引いておく。

ll N;
ll ret=0;
ll mo=1000000007;

ll rev(ll a) {
	ll r=1, n=mo-2;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
ll fact[2020200];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	fact[0]=1;
	for(i=1;i<=2*N+2;i++) fact[i]=fact[i-1]*i%mo;
	
	cout<<(mo-1+fact[2*N+2]*rev(fact[N+1])%mo*rev(fact[N+1]))%mo<<endl;
}

まとめ

最終的にCombination1個で解けるのが面白かった。