この問題は AtCoder Algorithm Lectures の 区間クエリのためのモノイド設計 5.3. ABC 部分列の個数 で解説されている問題の類題です。

上記記事の第 3 章にも書いてある通り、セグメント木の型 \(S\) ・二項演算 \(\mathrm{op}\) ・単位元 \(e\) を決めるための考え方として、

• 数列 \(X\) に関する必要な情報を \(f(X)\) 、
• 数列 \(X\) と数列 \(Y\) をこの順に結合してできる数列を \(XY\)

のように表す時に、

• \(S\) : \(f(X)\) を表す型
• \(\mathrm{op}\) : \(f(XY)\) を \(f(X)\) と \(f(Y)\) から求める関数。言い換えると、\(\mathrm{op}(f(X), f(Y)) = f(XY)\) を満たす関数。
• \(e\) : 空列の情報

が成り立つように設計する点がポイントでした。

この点を踏まえて今回の問題を考えてみます。

文字列 \(S\) と数列 \(A\) の組 \(X=(S,A)\) に対して、\(1 \leq i \lt j \lt k \leq |S|\) かつ \(S_i S_j S_k =\) RGB である \((i,j,k)\) の組すべてに対する \(A_i A_j A_k\) の総和を \(998244353\) で割った余りを \(\mathrm{RGB}(X)\) と書きます。\(\mathrm{RGB}(XY)\) を計算するために \(X, Y\) について必要な情報を考えましょう。\(XY\) に含まれる RGB 部分列は以下の \(4\) 通りに場合分けできます：

• RGB の \(3\) 文字を \(X\) から選ぶ。
• RG を \(X\) から、B を \(Y\) から選ぶ。
• R を \(X\) から、GB を \(Y\) から選ぶ。
• RGB の \(3\) 文字を \(Y\) から選ぶ。

よって、\(\mathrm{RG}(X), \mathrm{GB}(X), \mathrm{R}(X), \mathrm{B}(X)\) を \(\mathrm{RGB}(X)\) と同様の方法で定義した時に、

\[\mathrm{RGB}(XY) = \mathrm{RGB}(X) + \mathrm{RG}(X) \times \mathrm{B}(Y) + \mathrm{R}(X) \times \mathrm{GB}(Y) + \mathrm{RGB}(Y)\]

が成り立ちます。ただし、ここでの計算はすべて \(998244353\) を法として行います。よって整数の \(5\) 個組

\[(\mathrm{RGB}(X), \mathrm{RG}(X), \mathrm{GB}(X), \mathrm{R}(X), \mathrm{B}(X))\]

を \(f(X)\) と定義するのが一見よさそうですが、実はこれだと失敗してしまいます。というのも、このように定義すると \(f(X), f(Y)\) から \(\mathrm{RGB}(XY)\) を計算することは出来るのですが、\(\mathrm{op}\) は

\[\mathrm{op}(f(X), f(Y)) = f(XY)\]

を満たす、すなわち \(f(X), f(Y)\) から \(f(XY)\) 全体を計算できる必要があるのでした。この点について考えてみると、\(\mathrm{RG}(XY), \mathrm{GB}(XY)\) が \(f(X), f(Y)\) から計算できないことに気づきます。そこで \(\mathrm{G}(X)\) をこれまでの関数と同様に定義して

\[(\mathrm{RGB}(X), \mathrm{RG}(X), \mathrm{GB}(X), \mathrm{R}(X), \mathrm{G}(X), \mathrm{B}(X))\]

を \(f(X)\) と置くことにすると、今度こそ \(f(X), f(Y)\) から \(f(XY)\) を計算できるようになり、以下に挙げるようなモノイド設計に成功します。

#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

struct S {
  mint ABC, AB, BC, A, B, C;
};

S op(S x, S y) {
  S z;
  z.ABC = x.ABC + x.AB * y.C + x.A * y.BC + y.ABC;
  z.AB = x.AB + x.A * y.B + y.AB;
  z.BC = x.BC + x.B * y.C + y.BC;
  z.A = x.A + y.A;
  z.B = x.B + y.B;
  z.C = x.C + y.C;
  return z;
}

S e() { return {0, 0, 0, 0, 0, 0}; }

以上の内容に基づいて実装を行えば問題を解くことができます。計算量は \(\mathrm{O}(N + Q \log N)\) で十分高速です。

• 実装例, C++