連呼 [いろはちゃんコンテスト Day2 E]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_e

解説

https://atcoder.jp/contests/iroha2019-day2/submissions/5214793

数えやすい方を数えよう。
AAAを連続する部分文字列に持つ組み合わせではなく、持たない方の組み合わせを考えてみよう。
とりあえず、組み合わせ全体は先頭がA, 末尾がBと固定になっていて、他の部分なので、C(N+M-2, N-1)となる。
ここから、持たない方の組み合わせを引けば答えになる。
　
持たない場合というのはAとAAからなる場合になる。
ここでAAの個数を全探索して、全ての状態を数え上げよう。
AAの個数をaaとすると、Aの個数aはN-aa*2となる。
そして、AAとAの間と末尾には必ずBが1つは入るので、aa+a+1個のBは場所が確定する。
組み合わせで計算することになる部分は、AAとAの順番と、場所が確定していない残りのBの置き方である。
AAとAの順番はC(aa + a, aa)となる。
場所が確定していない残りのBの置き方はちょうど、重複組合せで計算ができる。
具体的にはH(aa+a, M-(aa+a) )である。
これを全てのAAの個数について計算して、全部引けば答え。

int N, M;
Comb<mint, 401010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
 
	mint ans = com.aCb(N + M-2, N-1);
	rep(aa, 0, N / 2 + 1) {
		int a = N - aa * 2;
 
		mint cmb = com.aCb(aa + a, aa);
		int b_space = aa + a;
 
		int b_rest = M - (aa + a);
 
		if (b_rest < 0) continue;
 
		cmb *= com.nHk(b_space, b_rest);
 
		ans -= cmb;
	}
 
	cout << ans << endl;
}