Codeforces #195 Div2. D. Vasily the Bear and Beautiful Strings

Dはちょっと手こずった問題。
http://codeforces.com/contest/336/problem/D

問題

0がN個、1がM個からなる文字列Sがある。
この文字列が２文字以上の間、以下の処理を繰り返し行う。

• 最後２文字が00なら1に置換する
• 最後２文字が00以外なら0に置換する

上記処理を繰り返したとき、最後１文字なったときの文字列Gが0または1になるSの組み合わせは何通りあるか。

解法

N==0またはM==0の時を先に片づけておく。

• N==0なら、S=111111...に対し処理を行うと、M==1ならG=1、それ以外はG=0となる。
• M==0なら、S=000000...に対し処理を行うと、Mが偶数ならG=1、奇数ならG=0となる。

最後にN>0、M>0の時を考える。
0がN個、1がM個の時、最後0に変換できる組み合わせをP[0][N,M]と書くことにする。
最後1に変換できるのは同様にP[1][N,M]。
P[0][N,M]+P[1][N,M]は全組み合わせなのでになる。

最後がG==0になるのは直前が01,1*のいずれかの時なので、
P[0][N,M] = P[1][N-1,M] + P[0][N,M-1] + P[1][N,M-1] = - P[0][N-1,M] + = - P[0][N-1,M] = - P[0][N-1,M]
と結局変数Nだけが変化する漸化式ができるので、O(N)でP[0][N,M]を計算できる。

もNが変化していくので、N-1の結果を使ってNの時の値を求めればO(1)で計算できる。

int N,M,G;
ll mo=1000000007;
vector<ll> rev;

vector<ll> list_mod_inverse(ll n, ll m) {
	vector<ll> inv(n + 1);
	inv[1] = 1;
	for (int i=2;i<=n;++i) inv[i] = inv[m % i] * (m - m / i) % m;
	return inv;
}

void solve() {
	int f,i,j,k,l, x,y;
	ll r=0;
	
	cin>>N>>M>>G;
	
	if(M==0) {
		cout << ((N%2)!=G) << endl;
		return;
	}
	if(N==0) {
		G^=(M!=1);
		cout << G << endl;
		return;
	}
	
	rev = list_mod_inverse(200001,mo);
	
	// P0(0,M)
	ll ret=(M!=1);
	ll tot=1;
	
	FOR(i,N) {
		tot = tot*(i+1+M) % mo; 
		tot = tot*rev[i+1] % mo; 
		
		ret = (((tot - ret)%mo)+mo)%mo;
	}
	
	if(G==1) {
		ll tot=1;
		// C[N+M][M]
		FOR(i,M) tot=(tot*(N+M-i) % mo) *rev[i+1]%mo;
		ret = (mo+tot-ret)%mo;
	}
	cout << ret << endl;
}

まとめ

list_mod_inverseはTwitterで見つけた1～(P-1)のmod Pにおける逆元を1つO(1)、全部でO(P)で求める手法を使わせてもらいました。