条件を満たす文字列の RG を K と置き換えると、この問題は以下のように言い換えられます。

\(K\) 個の K、\(R-K\) 個の R、\(G-K\) 個の G、\(B\) 個の Bを並び替えて得られる文字列であって、部分文字列 RG を含まないものの個数を求めよ。

言い換え後の問題にたいする二つの解法を紹介します。

[1] 包除原理

RG の個数について包除原理を適用することで解くことができます。

\(N=R+G+B\) と置きます。\(\lbrace 1,2,\ldots,N-1\rbrace\) のサイズ \(k\) の部分集合 \(T\) 全てに対する、\(i\in T\Rightarrow\) \(S_iS_{i+1}=\)RG を満たすような文字列の個数の総数の総和は多項係数として \(\mathrm{O}(1)\) で求められます。

包除原理で必要な値は上の値を \(k=0,1,\ldots,\min({R-K,G-K})\) で動かしたときの値なので、 \(\mathrm{O}(R+G+B)\) で解くことができます。

実装例(c++)

[2] 組み合わせ的解釈

はじめに K,G,B を自由に並べます。次に、R を挿入することにすると、G の左隣以外の任意の場所に挿入できます。どちらについても二項係数、多項係数を用いて簡単に求めることができます。計算量は \(\mathrm{O}(R+G+B)\) です。

余談ですが、こちらの方針の場合高速な階乗計算を用いることで、\(P=998244353\) として計算量 \(\mathrm{O}(\sqrt P\log P)\) で解くことも可能です。

\(\mathrm{O}(R+G+B)\) の実装例(c++)