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

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

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

[1] 包除原理

RG の個数について包除原理を適用することで解くことができます。RG が少なくとも \(i\) 個存在するような文字列の個数は、多項係数として求められます。計算量は \(\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++)