読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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

Codeforces

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

問題

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

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

上記処理を繰り返したとき、最後1文字なったときの文字列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]は全組み合わせなので{}_{N+M} C {}_Nになる。

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

{}_{N+M} C {}_Nも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)で求める手法を使わせてもらいました。

広告を非表示にする