最高に面白い
問題
解法
重要な観察として，すぬけ君が動ける範囲はBが来るたびに半分以下になるというのがある．最終的にすぬけ君が勝つ，すなわちすぬけ君の動ける範囲が1マス以上あるためには，Bを置く回数は\(O(\log n)\)回程度でなければならない．
すぬけ君が勝つような文字列を数え上げて，\(2^Q\)からそれを引くという方針が立つ．\(i\)回目の操作のあとすぬけ君の動ける範囲が\(k\)マスの時，\(i-k\)回目の操作後すぬけ君が\(2k\)マス動ける状態にあり，また\(i-k\)回目以降にBが来ない．知りたいのは\(n\)回目の操作のあとすぬけ君が1マス以上動ける文字列の数だから，
\[
dp[i][j] := \text{\(i\)回目の操作後すぬけ君が\(2^j\)マス以上動ける状態にある文字列の数}
\]
としてDPをすればよい．
遷移は，
\[
dp[i][j] \leftarrow dp[i][j] + \begin{cases}
dp[i - 2^j][j + 1] & \text{if \(s[i] = B\) and \(s[i - 2^j...i-1]\) doesn't contain B} \\
dp[i-1][j] & \text{if } s[i] = S
\end{cases}
\]
みたいな感じになる．?ならどっちもやる．Bが区間に含まれるかどうかの判定は累積和でやる．
感想
2冪だけ覚えておくだけでいいのすごく非直感的．めちゃくちゃ面白い問題だと思った．コンテスト中にこういうのが通せるようになりたいなあ
