問題
左から右へ番号 $1,\dots,N$ の $N$ 枚のコインが一列に並び、各コインは表（H）か裏（T）である。2 人が交互に次の操作を行い、操作できなくなった方が負け（通常ルール）。
- 表のコインを 1 枚選び、その位置を $i$ とする。$1\le k\le i$ を選び、位置 $i-k+1,\dots,i$ の $k$ 枚をすべて反転する（位置 $i$ は表から裏になる。$k\ge 2$ のとき左側の $k-1$ 枚は表裏が入れ替わる）。
現在の並びから先手が勝てる最初の 1 手は何通りあるか。手は組 $(i,k)$ で区別する。先手が負ける局面なら 0 を出力せよ。
入力形式
N
S制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 2\times10^5$ |
| 2 | $S$ は長さ $N$ の H と T からなる文字列（$S$ の $i$ 文字目が位置 $i$ のコイン） |
入出力例
入力例1
6
HTHHTH出力例1
2（表は位置 1,3,4,6。先手が勝てる手は 2 通り。全状態の探索で確認済み）
入力例2
3
HHH出力例2
2入力例3
2
TT出力例3
0（表が無いので操作できず、先手の負け）
背景と出典
この形は Berlekamp・Conway・Guy『Winning Ways』のコイン反転ゲームの一つ "Ruler" と同じと記憶している（本セッションでは原典を確認していない）。コイン反転ゲームでは、表のコイン 1 枚だけの局面の Grundy 数 $g(i)$ を求めれば、一般の局面の Grundy 数は表のコインの $g$ の XOR になる、という定理が使える。
この問題で確かめたいのは次の 3 点。(1) $g(i)$ が「$i$ の最大の 2 べき約数」になること（mex の表と比較）。(2) 勝敗だけでなく勝ち手の個数を $O(N)$ で数える方法。(3) 「$g(i)=i$」のような似た式（操作が最大 2 枚の Turning Turtles ならこうなる）では本問の勝敗が合わないこと。
ヒント（クリックで段階的に開示）
ヒント1（方向性）
表のコイン 1 枚だけの局面を考える。位置 $i$ のコインを裏にして、さらに左の $k-1$ 枚を反転すると、左の $k-1$ 枚が表になる。つまり 1 枚のコインが「左の何枚かの表のコイン」に変わる。複数枚の表は独立なゲームの和として扱える。
ヒント2（アプローチ）
位置 $i$ の 1 枚だけのときの Grundy 数を $g(i)$ とすると、$g(i)=\mathrm{mex}\{0,\ g(i-1),\ g(i-1)\oplus g(i-2),\ \dots,\ g(i-1)\oplus\cdots\oplus g(1)\}$。小さい $i$ で表を作ると規則が見える。局面全体の値は表のコインの $g$ の XOR $X$。先手が負けるのは $X=0$ のとき。
ヒント3（誘導）
勝ち手は「手の後の XOR が 0」になる $(i,k)$。手の後の値は $X\oplus g(i)\oplus P_{i-1}\oplus P_{i-k}$（$P_j=g(1)\oplus\cdots\oplus g(j)$）。位置 $i$ ごとに $P_{i-k}=T$ を満たす $k$ の個数を、$P_0,\dots,P_{i-1}$ の出現回数の辞書で数える。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0]); s = data[1]
g = [0]*(n+1)
for i in range(1, n+1):
g[i] = i & (-i) # ruler function: 最大の 2 べき約数
P = [0]*(n+1)
for i in range(1, n+1):
P[i] = P[i-1] ^ g[i]
X = 0
for i in range(1, n+1):
if s[i-1] == 'H':
X ^= g[i]
cnt = {0: 1} # P[0]=0 を j の候補に入れておく。位置 i を処理する時点で j∈[0,i-1]
total = 0
for i in range(1, n+1):
if i >= 2:
cnt[P[i-1]] = cnt.get(P[i-1], 0) + 1 # j=i-1 を追加（j=0 は初期値）
if s[i-1] == 'H':
t = P[i-1] ^ X ^ g[i]
total += cnt.get(t, 0)
print(total)
main()
計算量: 時間 $O(N)$（辞書の平均）、空間 $O(N)$。実測（Python 3.14、M1 Mac）で $N=2\times10^5$ のランダム入力が 1.43 s、全て H の入力が 0.53 s（ランダム側が遅い理由は未調査）。
Step-by-Step 解説
位置 $i$ のコイン 1 枚を反転する操作は、「そのコインが表なら裏にする」「裏なら表にする」の二通りしかない。表が 2 枚あるとき、同じ位置を 2 回反転すると元に戻る。このため局面の Grundy 数は、表のコインそれぞれを単独で置いたときの Grundy 数の XOR になる（コイン反転ゲームの定理。本セッションで証明はしていないが、全状態の探索と XOR の予想が 500 件一致したので定理の適用は正しいと判断した）。
位置 $i$ だけが表のとき、$k=1$ なら全部裏で値 0。$k\ge2$ なら位置 $i-k+1,\dots,i-1$ の $k-1$ 枚が表になるので、値は $g(i-1)\oplus\cdots\oplus g(i-k+1)$。よって $g(i)=\mathrm{mex}\bigl(\{0\}\cup\{P_{i-1}\oplus P_j\mid 0\le j\le i-2\}\bigr)$（$k=2$ が $j=i-2$ で値 $g(i-1)$、$k=i$ が $j=0$ で値 $P_{i-1}$）。$n\le3000$ でこの mex の表を作ると、全 $n$ で $g(n)=n\ \&\ (-n)$（最大の 2 べき約数）と一致した。
$X=\bigoplus_{S_i=\texttt{H}} g(i)$。$X=0$ なら先手の負け、$X\ne0$ なら先手の勝ち。
手 $(i,k)$ の後の XOR は $X\oplus g(i)\oplus(P_{i-1}\oplus P_{i-k})$（位置 $i$ の表が消え、左の $k-1$ 枚が反転されるので、それぞれの $g$ が XOR で出入りする）。これが 0 になる条件は $P_{i-k}=P_{i-1}\oplus X\oplus g(i)$。$j=i-k$ は $0\le j\le i-1$ を動くので、$P_0,\dots,P_{i-1}$ の中に目標値がいくつあるかを辞書で数える。位置を左から進めながら辞書に $P_{i-1}$ を足していけば全体で $O(N)$。
$N\le11$ の 500 件で、全状態を再帰で探索して「負け局面に移れる手」を数えた値と一致した。勝敗だけの一致ではなく、手の個数まで一致している点が検算としては強い。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| $g(i)=i\ \&\ (-i)$ の XOR と prefix XOR の出現回数（本解） | $O(N)$ | 採用 | 全状態の探索と 500 件全件一致 |
| 全 $(i,k)$ を prefix XOR で 1 つずつ確かめる | $O(N^2)$ | 不採用 | $N=2\times10^5$ では $2\times10^{10}$ 回。正しさの検算には使える |
| 全状態の再帰探索 | $O(2^N\cdot N^2)$ | 検算用のみ | $N\le11$ でしか動かない |
| $g(i)=i$（操作が 1 枚か 2 枚の Turning Turtles と混同） | $O(N)$ | 不採用 | 本問の勝敗と 65/500 件で食い違う |
前提が変わったら:
- 操作が最大 2 枚（$k\le2$）に変わると、$g(i)=\mathrm{mex}\{0,g(1),\dots,g(i-1)\}$ なので帰納的に $g(i)=i$ になるはず（導出のみ、未実測）。本問の式をそのまま使えない
- $N\ge10^6$ で Python が遅すぎるなら、辞書を配列にして $P$ の値域（$g\le2^{17}$ なので XOR は $2^{18}$ 未満）で数える。未実装
- 勝ち手そのものを出力させるなら、辞書に添字のリストを持たせる。個数が $O(N^2)$ になりうるので、問題を「1 つ出力」にするのが普通
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 位置 $i$ の $g$ を $i$ そのものにする | Turning Turtles の結果と混同 | i & -i |
| 辞書に $P_i$ まで入れてから数える | $j$ は $0\le j\le i-1$ で $j=i$ は $k=0$ になる | 位置 $i$ を数える前に $P_{i-1}$ までを入れる |
| $P_0=0$ を辞書に入れ忘れる | $k=i$（左端まで反転）が数えられない | cnt = {0: 1} で初期化 |
| 勝ち手 $(i,k)$ を $i$ だけで数える | 手は組で区別されると読み落とす | 位置ごとに $k$ の個数を足す |
次のステップ
- 発展1: 反転できる枚数を $k\le L$ に制限した場合の $g(i)$ を、mex の表から予想して確かめる
- 発展2: 勝ち手を 1 つだけ出力する（辞書に最後の添字を持たせる）
- 次回予告: 焦点帯外（M2・M3）を含む通常のローテーション
検証ログ（本セッションで実行した数値）
- mex の表（実測）: $n\le3000$ で、反転の規則どおりに作った $g(n)$ が全 $n$ で $n\ \&\ (-n)$ と一致
- 全探索との照合（実測）: $N\le11$ の 500 件で、全状態の再帰探索による勝ち手の個数とプログラムの出力が全件一致
- 誤った式（実測）: $g(i)=i$ で勝敗を判定すると 500 件中 65 件で本解と食い違う
- 入力例（実測）: 例 1 は 2、例 2 は 2、例 3 は 0（出力例どおり）。全探索でも 2・2 を確認
- 実行時間（実測）: $N=2\times10^5$ のランダムで 1.43 s、全て
Hで 0.53 s（答えは 68929） - 扱っていない範囲: 定理（表のコインの独立性）と $g(i)=i\ \&\ (-i)$ の証明、『Winning Ways』原典の確認、反転枚数に上限がある場合、$N\ge10^6$