文字列 \(S\) の先頭 \(i\) 文字からなる文字列を \(S[0:i]\) と表すことにします。ただし、\(i>|S|\) のとき「\(S\) の先頭 \(i\) 文字からなる文字列」は、\(S\) をprefixとし、かつ \(S\) をprefix とするどのような文字列とも異なると定めます。

問題の読み替え

問題を次の通り読み替えます。

問題：\(S\) に含まれる ? を、英大文字・英小文字の \(52\) 種の文字にそれぞれ独立にランダムに変化させたとき、\(S\) が DDoS 型文字列を部分列に持つ確率はいくらか？

この問題の答えに \(52^q\) を掛けると元の問題の答えを得ることができます。

この読み替えは必須ではありませんが、数え上げの問題を確率の問題に、あるいはその逆に読み替えることで見通しが良くなることはしばしばあります。

例：ABC200 F、第6回 ドワンゴからの挑戦状 予選 C

単純な問題

まずは、元の問題を単純化した次の問題を考えます。

問題：元の問題と同様の設定の下、(DDoS 型文字列ではなく) DDoS を部分列に持たないような確率を求めてください。

この問題は次のようなDPで解くことができます。

\(DP[i][j]\) = \(S[0:i]\) の ? を置換してできる長さ \(i\) の文字列が、DDoS\([0:j]\) を部分列に持ち、かつ DDoS\([0:j+1]\) を部分列に持たないものになる確率

元の問題

元の問題でも単純な問題と同様のDPを考えてみます。

\(DP[i][j]\) = \(S[0:i]\) の ? を置換してできる長さ \(i\) の文字列が、ある DDoS 型文字列の \(j\) 文字目までを部分列に持ち、かつ どのような DDoS型文字列の \(j+1\) 文字目までも部分列に持たないものになる確率

この DP は、\(j=1\) である文字列の末尾に大文字を追加したケースを除き、単純な問題と同様に遷移を計算することができます。

\(j=1\) である文字列の末尾に大文字を追加したケースを考えます。このとき、追加した大文字がすでに文字列に含まれているかどうかで遷移先が変わるため、上で定義したDPでは適切に扱うことができません。
一見するとどの大文字がすでに文字列に含まれているかの情報を持つ必要があるように思えますが、種類は不要であり種類数の情報さえ持てば十分です。

具体的な遷移を考えることで、種類数の情報を持てば十分なことを確かめましょう。\(DP[i][1]\) に数えられるような文字列 \(T\) の末尾に大文字 \(c\) が追加されて \(T'\) になったとき、\(T'\) が \(DP[i+1][*]\) のいずれに数えられるかを考えます。
\(S[0:i]\) に含まれる大文字の種類数を \(x\)、\(T\) に含まれる大文字の種類数を \(y\) とします。
\(c\) が \(S[0:i]\) に含まれるとき、\(DP[i+1][2]\) に遷移します。
そうでなく、\(c\) が \(T\) に含まれるのは、\(c\) が \(y-x\) 種のいずれかの文字列であるときです。よって \(T\) がそのような文字列である確率は \(x=26\) のとき \(0\) 、そうでないとき \(\frac{y-x}{26-x}\) です。
以上により確かめられました。

まとめ

以下のような29状態のDPで解くことができます。

\(DP[i][state]\) = \(S[0:i]\) の ? を置換してできる長さ \(i\) の文字列のうち、以下の各 state に該当する文字列の個数(または確率)

• 大文字を含まない
• 大文字をちょうど \(y\) 種含み、どの大文字もちょうど \(1\) 度だけ含む \((y=1,2,\ldots,26)\)
• \(2\) 度以上含まれる大文字が存在し、それ以降に小文字を含まない
• \(2\) 度以上含まれる大文字が存在し、それ以降に小文字を含み、それ以降に大文字を含まない

Writer解(C++)