Codeforces 336D - Vasily the Bear and Beautiful Strings

問題文 : Vasily the Bear and Beautiful Strings

問題概要 :

つぎの性質を満たす文字列$s$ の総数をmod $10^9+7$ で求めよ.

・$0$ が$n$ 個, $1$ が$m $ 個から成る文字列である.
・$s$ にmodification を0 回以上行うことで最終的に文字列$s$ が文字$g$ になる. modification とは, 文字列$s$ の末尾の$2$ 文字を$1$ 文字に置き換える操作で, $2$ 文字とも$0$ ならば$1$ に, そうでなければ$0$ に置き換える.

$n,\ m \leqq 10^5,\ 0 \leqq g \leqq 1$

解法 :
つぎのように場合分けして考える.

・$n = 0$ のとき
$n = 0$ ならば, $m = 1$ かつ$g = 1$ である場合,または $m > 1$ かつ$g = 0$ のとき条件を満たす文字列"1111....1" が1 通りのみ存在.

・$m = 0$ のとき
$m = 0$ ならば, $n$ が奇数かつ$g = 0$ である場合, または $n$ が偶数かつ$g = 1$ のとき条件を満たす文字列"0000....0" が1 通りのみ存在.

・$n > 0,\ m > 0$ のとき
まず, $g=0$ ならば, "1" から始まる$2$ 字以上の文字列はすべてmodification を行うことで$0$ になるので$_{n+m-1}\text{C}_{m - 1}$通り, そして$0$ から始まるときは$n - 1$個の$0$, $m $個の$1$ があって, modification の結果が$1$ となるような文字列の総数を足せば良い.

$g=1$ならば, $_{n+m-1}\text{C}_{m}$ (全体) - $g=0$, $n$個の$0$, $m$ 個の$1$ のときの総数を引けば良い.

n, m について減少していく計算で, $n$ の値に依存する再帰をすればよく, $O(n)$ でこの問題を解くことができる.

#include <cstdio>

using namespace std;

typedef long long lint;
const int MOD = 1000000007;

lint perm[200001];

lint pow(lint a, lint n)
{
	lint ret = 1;
	while (n){
		if (n & 1) ret = (ret * a) % MOD;
		a = (a * a) % MOD;
		n >>= 1;
	}
	return (ret);
}

lint comb(int n, int k)
{
	if (n <= 0 || n < k) return (0);
	return ((perm[n] * pow((perm[k] * perm[n - k]) % MOD, MOD - 2)) % MOD);
}

lint recur(int n, int m, int g)
{
	lint ans = 0;
	
	if (n == 0) return ((m == 1 && g == 1) || (m != 1 && g == 0));
	if (m == 0) return (g == (n + 1) % 2);
	
	if (g == 0){
		ans = (ans + comb(n + m - 1, m - 1)) % MOD;
		ans = (ans + recur(n - 1, m, 1 - g)) % MOD;
	}
	else {
		ans = (ans + comb(n + m, n) - recur(n, m, 1 - g) + MOD) % MOD;
	}
	
	return (ans);
}

int main()
{
	int n, m, g;
	
	perm[0] = 1;
	for (int i = 1; i <= 200000; i++)
		perm[i] = (perm[i - 1] * i) % MOD;
	
	scanf("%d %d %d", &n, &m, &g);
	
	printf("%lld\n", recur(n, m, g));
	
	return (0);
}