Codeforces 336D Vasily the Bear and Beautiful Strings

問題

01からなる文字列で、0がn個1がm個ちょうど含まれているものを考える。
この文字列に対して、以下の操作を繰り返した後で、最後にgになるものの個数を求めよ。

操作：
文字列が1文字になっていたら終了
末尾が00のとき、1に置き換える
末尾が01のとき、0に置き換える
末尾が10のとき、0に置き換える
末尾が11のとき、0に置き換える

制約条件

n, m≦10^5
gは0または1

方針

0がn個, 1がm個で、最後に0になる文字列の個数をa(n, m)、
最後に1になる文字列の個数をb(n, m)と置く。

すると、b(n, m) = a(n-1, m)である。
（評価して1になる文字列は、最後の1文字が0で、それ以外の評価は0になるしかない）

また、a(n, m) + b(n, m) = C(n + m, n)であるので、
a(n, m) = C(n + m, n) - b(n, m) = C(n + m, n) - a(n - 1, m)
という漸化式ができる。

これを使ってnが0になるまでnを減らせば、a(0, m)はO(1)で計算できるので、
結局O(n)でa(n, m)が計算できる。

ソースコード

const int mod = (int)1e9 + 7;
ll fact[220000];
ll pw(ll n, ll m){
	ll res = 1;
	for(; m; m >>= 1){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
ll inv(ll n){ return pw(n, mod - 2); }
ll C(ll n, ll m){
	return fact[n] * inv(fact[m]) % mod * inv(fact[n - m]) % mod;
}

ll calc(int n, int m){
	if(n == 1 && m == 0) return 1;
	if(n == 0) return m == 1 ? 0 : 1;
	return (C(n + m, n) - calc(n - 1, m) + mod) % mod;
}

int main(){
	fact[0] = 1;
	rep(i, 220000-1) fact[i + 1] = fact[i] * (i + 1) % mod;
	
	int n, m, g;
	cin >> n >> m >> g;
	
	cout << (g ? (C(n + m, n) - calc(n, m) + mod) % mod : calc(n, m)) << endl;
	
	return 0;
}