ABC #104 D
ABC 数と同様に A 数, AB 数を考える.
\(i\) 文字目まで見たときの A 数, AB 数, ABC 数をそれぞれ \(A(i), B(i), C(i)\) とする.
このとき, 以下のようになる.
\(i\) 文字目が A
のとき:
ここで \(q\) は今までに現れた ?
の数である. ?
で枝分かれした木を考えると, すべての葉に A
を追加することになるので, \(3^q\) を追加することになる.
\(i\) 文字目が B
のとき:
\(i\) 文字目が C
のとき:
\(i\) 文字目が ?
のとき:
各式の係数 \(3\) は枝分かれによって増える分を考慮している.
これを DP で計算して \(C(\vert S \vert)\) を求める.