答えの式を多変数形式的冪級数を用いて導出します．

用いる記号

• \(p \coloneqq 998244353 \) とおき，主に3変数形式的冪級数環 \(\mathbb{F}_p[[x, y, z]]\) 上で考えます．
  • 文字列中の R, G, B の個数をそれぞれ \(x\), \(y\), \(z\) の次数に，文字列の場合の数を係数に持ちます．
• 以下のように係数を取り出す演算を表します．
  • \(F \in \mathbb{F}_p[[x]]\) に対し \([x^i]F\) で \(F\) の \(x^i\) の係数を表します．
  • \(F \in \mathbb{F}_p[[x, y, z]]\) に対し \([x^i y^j z^k]F\) で \(F\) の \(x^i y^j z^k\) の係数 \((\in \mathbb{F}_p)\) を表します．
  • \(F \in \mathbb{F}_p[[x, y, z]]\) に対し \([z^k]F\) で \(F\) の \(z^k\) の係数 \((\in \mathbb{F}_p[[x, y]])\) を表します．
    • ここでは \(\mathbb{F}_p[[x, y, z]]\) をこれと同型な \(\mathbb{F}_p[[x, y]]\,[[z]]\) と同一視しています．
    • 一般に，多変数形式的冪級数から一部の変数についての係数を取り出す演算も同様の同一視により正当化できます．
• 二項係数は \(\binom{n}{r}\) で表します．

負の二項定理

以下の式が成り立ちます．

\[ [x^i] \left( \frac{1}{1-rx} \right)^{d+1} = \binom{i + d}{d} r^i. \]

証明は https://maspypy.com/多項式・形式的べき級数（３）線形漸化式と形式 などを参照してください．

\(K=0, B=0\) の場合

まず「R を \(i\) 個，G を \(j\) 個，B を \(0\) 個含んでいて，RG が連続部分列として \(0\) 個含まれる文字列の個数」が \([x^i y^j]F_1\) となる \(F_1 \in \mathbb{F}_p[[x, y]]\) を考えます．

B を \(0\) 個含み RG が連続部分列として \(0\) 個含まれる文字列（文字列1と呼びます）は

1. G を \(0\) 個以上並べる
2. その後ろに R を \(0\) 個以上並べる

として得られるので，

\[ \begin{aligned} F_1 &= \left(\sum_{j \ge 0} y^j \right) \left(\sum_{i \ge 0} x^i \right) \\ &= \frac{1}{(1-x)(1-y)} \end{aligned} \]

とわかります．

\(K=0\) の場合

次に「R を \(i\) 個，G を \(j\) 個，B を \(k\) 個含んでいて，RG が連続部分列として \(0\) 個含まれる文字列の個数」が \([x^i y^j z^k]F_2\) となる \(F_2 \in \mathbb{F}_p[[x, y, z]]\) を考えます．

RG が連続部分列として \(0\) 個含まれる文字列（文字列2と呼びます）は

1. 文字列1をおく
2. 以下を \(0\) 回以上繰り返す
   1. その後ろに B を並べる
   2. その後ろに文字列1を並べる

として得られるので，

\[ \begin{aligned} F_2 &= F_1 \sum_{k \ge 0} (z F_1)^k \\ &= \frac{F_1}{1 - F_1 z} \end{aligned} \]

とわかります．

一般の場合

最後に「R を \(i\) 個，G を \(j\) 個，B を \(k\) 個含んでいて，RG が連続部分列として \(K\) 個含まれる文字列の個数」が \([x^i y^j z^k]F_3\) となる \(F_3 \in \mathbb{F}_p[[x, y, z]]\) を考えます．

RG が連続部分列として \(K\) 個含まれる文字列は

1. 文字列2をおく
2. 以下を \(K\) 回繰り返す
   1. その後ろに RG を並べる
   2. その後ろに文字列2を並べる

として得られるので，

\[ \begin{aligned} F_3 &= F_2 (xy F_2)^K \\ &= x^K y^K F_2^{K+1} \end{aligned} \]

とわかります．

よって答えは負の二項定理を用いて

\[ \begin{aligned} [x^R y^G z^B] F_3 &= [x^{R-K} y^{G-K} z^B] F_2^{K + 1} \\ &= [x^{R-K} y^{G-K}] F_1^{K+1} [z^B] \left( \frac{1}{1 - F_1 z} \right)^{K+1} \\ &= [x^{R-K} y^{G-K}] \binom{B + K}{K} F_1^{K+1+B} \\ &= \binom{B + K}{K} [x^{R-K} y^{G-K}] \frac{1}{(1-x)^{K+B+1} (1-y)^{K+B+1}} \\ &= \binom{B + K}{K} \left( [x^{R-K}] \frac{1}{(1-x)^{K+B+1}} \right) \left( [y^{G-K}] \frac{1}{(1-y)^{K+B+1}} \right) \\ &= \binom{B+K}{K} \binom{R-K+K+B}{K+B} \binom{G-K+K+B}{K+B} \\ &= \binom{B+K}{K} \binom{R+B}{K+B} \binom{G+B}{K+B} \\ \end{aligned} \]

と求まります．

これらの二項係数は \(p\) を定数として \(\Theta(\max(B + K, R+B, G+B)) = \Theta(\max(R, G) + B)\) 時間で計算できます．