文字列 について、以下が成り立ちます。
「 が 個の "A"、 個の "B"、 個の "AB" を適当な順番で連結した文字列としてあり得る」
「 は 個の "A" と 個の "B" からなる長さ の文字列であり、部分文字列に "AB" が 個以上 個以下含まれる」
(証明は省きますが、
を示せばよく、証明自体はそこまで難しくないと思います)
よって、以下では「 個の "A" と 個の "B" からなる長さ の文字列であり、部分文字列に "AB" がちょうど 個含まれる」ような文字列を について数え上げ、それらを足し合わせることで元の問題の答えを求めることを考えます。
"AB" がちょうど 個含まれるような文字列はどのように数え上げれば良いでしょうか。
"AB" を "X" などに置換すると、それ以外に "AB" は登場しないことから文字列は以下のようになっていることがわかります。
...XB..(0個以上).BA..(0個以上).AX...
つまり、"X" と "X" の間、および "X" と文字列の端との間は、 個以上の "B" と 個以上の "A" がこの順で並んでいることがわかります。
"A" と "B" の置ける個数等は互いに影響しないため、結局は "A", "B" 独立に、 個の空間に 個(または 個)の球を入れる問題と同じであり、これは二項係数で求めることができます。
よってこの問題を解くことができました。
二項係数(または階乗等)を ほどで適切に前計算しておくことで、1 ケースあたりの計算量は となります。
def solve(a, b, c): res = 0 for k in range(c, c + min(a, b) + 1): res = (res + comb(a + c, k) * comb(b + c, k)) % (10**9 + 7) return res