A, B, C からなる文字列の A を \(1\)、B を \(2\)、C を \(3\) で置き換えてできる数列を以降では考えます。文字列に対する問題中の操作によって、その文字列に対応する数列全体の XOR の値は不変になることを利用します。\(S\) に対応する数列を \(A\) とします。

\(1, 2, 3\) からなる数列 \(X\) が、\(A\) に対する操作を繰り返して得られることは、以下の条件と同値です。

• \(A\) のある連続部分列への分割 \(B_1, B_2, \ldots, B_{|X|}\) が存在して、\(B_i\) 全体の XOR は \(X_i\) に等しく、かつ \(B_i\) に対して操作を繰り返すことで長さを \(1\) にできる

長さ \(2\) 以上の数列 \(B_i\) に対して操作を繰り返すことで長さを \(1\) にできることと、\(B_i\) が以下の \(2\) 条件を共に満たすことは同値であることが、帰納法などで示せます。

• \(B_i\) 全体の XOR が \(0\) ではない

• \(B_i\) は \(2\) 種類以上の数からなる

先述の不変量より、\(B_i\) の長さを \(1\) にしたときの要素は \(B_i\) 全体の XOR に一致します。

ここで \(X_1 = k\) であるような \(X\) について \(A\) の分割 \(B_1, B_2, \ldots, B_{|X|}\) を考えるとき、\(A\) の接頭辞を短い順に見ていって、最初に全体 XOR が \(k\) になるもの（かつ操作を繰り返して長さを \(1\) にできるもの）を貪欲に \(B_1\) として選んでしまっても基本的には問題ありません。というのも、\(B_1\) としてより長い数列を取ったとすると、貪欲に選んだものとの差分（XOR が \(0\)）を \(B_2\) の方に押し付けることで、\(B_1\) を貪欲に選んだもので置き換えることができるからです。 ただしこの方法は、\(B_2\) の長さが \(1\) であり、かつ貪欲に選んだものとの差分が全て \(B_2\) と同じ文字からなるときは上手くいきません。\(B_2\) を長さ \(1\) にすることができなくなるからです。このとき、以下の \(2\) つの場合に分けて考えます。

• \(A\) 中の \(B_2\) 以降に \(B_2\) と異なる数がある場合、それを利用して差分を削除できる。よってこの場合、相変わらず \(B_1\) を貪欲に選んでも問題ない

• そうでない場合、貪欲に選んだ \(B_1\) より先が全て同じ数（\(m\) 個あるとする）になっている。このとき、\(A\) に対して操作を繰り返してできる数列のうち、\(k\) で始まるものは、\(A_1\) とその数が等しければ \(1\) 個、そうでなければ \(\lfloor \frac{m}{2}\rfloor + 1\) 個ある

以上のような性質を考慮すると、\(\textrm{dp}[i][k] :=\)（\(A\) の \(i\) 文字目以降だけ考えたときに操作を繰り返してできる数列のうち、\(k\) で始まるものの個数）と定めて、\(\textrm{dp}\) の値を \(i\) の大きい順に計算していくことで、問題を解くことができます。