問題
英小文字からなる長さ $N$ の文字列 $S$ と、$Q$ 個の質問が与えられる。質問 $j$ は 3 つの整数 $a_j,b_j,c_j$ で、$S$ の $a_j$ 文字目から始まる長さ $c_j$ の部分文字列と、$b_j$ 文字目から始まる長さ $c_j$ の部分文字列が等しいかを問う（0 始まり）。等しければ Yes、異なれば No を出力せよ。
テストデータには、ハッシュの衝突を狙った入力が含まれる。 特に、法 $2^{64}$（64 ビット整数の自然なあふれ）のローリングハッシュは、基数をどの奇数にしても誤答する入力がある。
入力形式
N Q
S
a_1 b_1 c_1
...
a_Q b_Q c_Q制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 2\times10^5$、$1\le Q\le 2\times10^5$ |
| 2 | $S$ は英小文字のみ |
| 3 | $1\le c_j$、$0\le a_j,b_j$、$a_j+c_j\le N$、$b_j+c_j\le N$ |
入出力例
入力例1
8 4
abababba
0 2 4
0 2 5
5 6 1
1 3 3出力例1
Yes
No
Yes
Yes入力例2（生成手順で与える）
長さ 1024 の Thue–Morse 列 $T_{10}$（a から始めて「今の列＋その a/b を入れ替えた列」を 10 回繰り返す）と、その a/b を入れ替えた列をつなげた長さ 2048 の $S$。質問は 1 個で 0 1024 1024。
出力例2
No（例2 の 2 つの部分文字列は 1 文字目から異なる。しかし法 $2^{64}$ のハッシュでは、乱択した奇数の基数 100 個すべてで両者のハッシュ値が一致し Yes と誤答した（実測））
概念図：Thue–Morse と 2 の割り切れ方
ヒント（クリックで段階的に開示）
ヒント1（方向性）
ハッシュ $H(X)=\sum_i X_i\,B^{|X|-1-i} \bmod M$ で、2 つの異なる文字列が衝突する ⇔ 差の多項式 $\sum_i (X_i-Y_i)B^{|X|-1-i}$ が $M$ で割り切れる。$M=2^{64}$ なら「差が 2 で 64 回割り切れる」ような文字列の組を作れば、$B$ によらず衝突する。
ヒント2（アプローチ）
Thue–Morse 列は $T_{k+1}=T_k\overline{T_k}$（$\overline{\ \cdot\ }$ は a/b 入れ替え）。$D_k=H(T_k)-H(\overline{T_k})$ とおくと $D_{k+1}=D_k\,(B^{2^k}-1)$。$B$ が奇数なら $B^{2^i}-1$ は 2 で $i+2$ 回以上割り切れる（$i\ge1$）。
ヒント3（誘導）
法を素数 $p$ にすれば、差の多項式（次数 $<L$、恒等的に 0 でない）の根は高々 $L-1$ 個。基数 $B$ を $[0,p)$ から一様に選べば衝突確率は $(L-1)/p$ 以下。$p=2^{61}-1$ なら 1 回の比較で $10^{-13}$ 程度。基数は 実行時に乱択 する（固定すると、それを狙った入力を作れる）。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
import random
MOD = (1 << 61) - 1 # メルセンヌ素数 2^61-1
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
s = data[2] # bytes: s[i] は文字コード（整数）
base = random.randrange(1 << 20, MOD - 1) # 実行ごとに乱択（入力を見てから基数を選べない）
h = [0] * (n + 1)
pw = [1] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * base + s[i]) % MOD
pw[i + 1] = pw[i] * base % MOD
out = []
idx = 3
for _ in range(q):
a, b, c = int(data[idx]), int(data[idx + 1]), int(data[idx + 2])
idx += 3
# S[a, a+c) と S[b, b+c) のハッシュ
x = (h[a + c] - h[a] * pw[c]) % MOD
y = (h[b + c] - h[b] * pw[c]) % MOD
out.append("Yes" if x == y else "No")
print("\n".join(out))
main()計算量: 前計算 $O(N)$、質問 1 個 $O(1)$。実測で $N=Q=2\times10^5$ が user 0.39 s。誤答の確率は Step 4 の見積もりで全体 $2\times10^{-8}$ 以下（片側誤り: No を Yes と答えることだけが起こりうる）。
Step-by-Step 解説
$H(X)-H(Y)\equiv \sum_i (X_i-Y_i)B^{L-1-i}\pmod M$。これが 0 になるのが衝突。$M$ と $B$ の選び方で「どれくらい 0 になりにくいか」が決まる。
$T_{k+1}=T_k\overline{T_k}$、$\overline{T_{k+1}}=\overline{T_k}T_k$。$H(XY)=H(X)B^{|Y|}+H(Y)$ なので
$$D_{k+1}=\bigl(H(T_k)B^{2^k}+H(\overline{T_k})\bigr)-\bigl(H(\overline{T_k})B^{2^k}+H(T_k)\bigr)=D_k\,(B^{2^k}-1)$$
$D_0=\pm1$ より $D_k=\pm\prod_{i=0}^{k-1}(B^{2^i}-1)$。$B$ が奇数なら $B-1$ は偶数、$i\ge1$ で $B^{2^i}-1$ は 2 で $i+2$ 回以上割り切れる（$B^2-1=(B-1)(B+1)$ は 8 の倍数で、以後 2 乗するたびに $(B^{2^{i-1}}+1)$ が 2 を 1 個足す）。よって $2$ で割れる回数は $1+\sum_{i=1}^{k-1}(i+2)$ 以上で、$k=10$ で $1+63=64$。長さ $2^{10}=1024$ で、どの奇数の基数でも衝突する。
基数が偶数なら $B^{64}\equiv0$ なので、末尾 64 文字が同じ文字列はすべて衝突する（もっと簡単に破れる）。
乱択した奇数の基数 200 個で、$T_k$ と $\overline{T_k}$ が初めて衝突する $k$ を調べた。$k=6$: 2 個、7: 2 個、8: 15 個、9: 23 個、10: 158 個で、最大は 10（導出どおり）。偶数の基数では、先頭 36 文字が異なり末尾 64 文字が同じ 100 文字の組が衝突した。
$p=2^{61}-1$ は素数なので、差の多項式（次数 $L-1$ 以下、0 でない）の根は $\mathbb{F}_p$ 上で高々 $L-1$ 個。$B$ を一様乱択すれば 1 回の比較の衝突確率は $\le (L-1)/p$。本問の最大 $L=2\times10^5$、$Q=2\times10^5$ 回で合計しても $\le Q(L-1)/p\approx 1.7\times10^{-8}$。
Thue–Morse $T_{17}$（長さ 131072）と反転で 20 個の基数を試し、衝突 0。
長さ $2\times10^5$ のランダム文字列の長さ 20 の部分文字列（相異なるもの 199,981 個）のハッシュで、法 $10^9+7$ では衝突が 21 件（見積もり $n^2/2p\approx20.0$）。法 $2^{61}-1$ では 0 件（見積もり $8.7\times10^{-9}$）。「2 つを比べる」だけなら $10^9+7$ でも $L/p$ 程度だが、多数のハッシュ値を集合に入れて重複を探す 使い方では $n^2/p$ で効いてくる。
迷った他案と採らなかった理由
| 案 | 1 回の比較の誤り率 | 採否 | 理由 |
|---|---|---|---|
| 法 $2^{64}$（あふれ任せ）・奇数の基数 | 攻撃入力で 1（実測 100/100） | 不採用 | Step 2。速いが、対策された入力で確実に落ちる |
| 法 $10^9+7$ の 1 本 | $\le L/p\approx2\times10^{-4}$ | 不採用 | 比較が $2\times10^5$ 回あると合計の上界が 1 を超える。集合に入れる用途では実測 21 件衝突 |
| 法 $10^9+7$ と $998244353$ の 2 本 | $\le (L/p)^2$ 程度 | 不採用 | 安全だが 2 倍の計算。$2^{61}-1$ 1 本と同等以上の保証を得るには 2 本とも基数の乱択が要る |
| Z-algorithm／接尾辞配列＋LCP | 0（決定的） | 不採用 | 誤りは無いが、任意の 2 区間の比較には SA＋LCP＋RMQ が要り $O(N\log N)$ の前計算と実装量が大きい。確率 $10^{-8}$ を許せるならハッシュが短い |
| 法 $2^{61}-1$ ＋ 実行時に乱択した基数（本解） | $\le L/p\approx9\times10^{-14}$ | 採用 | 上界を式で書ける。Python の多倍長整数で乗算がそのまま書ける |
前提が変わったら: C++ では $2^{61}-1$ の積が 64 ビットを超えるので、__int128 か、$2^{61}-1$ の性質（$2^{61}\equiv1$）を使った上位・下位ビットの足し算で剰余を取る実装が要る。誤りが 1 回も許されない 用途（例: 重複排除の結果をそのまま保存する業務）では、ハッシュが一致した組だけ実際の文字列を比べる。誤りは 0 になるが、Yes が多い入力では 1 質問 $O(c)$ に戻る。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
C++ で unsigned long long のあふれを法にする | Thue–Morse で長さ 1024 から確実に衝突（Step 2） | 素数の法 |
| 基数を定数（131、911382323 など）に固定する | 固定の基数を狙った入力を作れる（素数の法でも差の多項式の根を狙える） | 実行時に乱択 |
| 基数を小さい範囲（例 256 未満）から選ぶ | 衝突確率の上界は「一様に選べる基数の数」で割った値。範囲が狭いと上界が大きい | $[2^{20}, p-1)$ など広い範囲から |
部分ハッシュで h[a+c] - h[a]*pw[c] の後に剰余を取らない | 負の値のまま比べて、等しい文字列を No と誤る | % MOD（Python は非負に正規化される） |
区間のハッシュを h[a+c] - h[a] にする | 前半の $h[a]$ は $B^{c}$ 倍されて $h[a+c]$ に入っているので、桁がそろわない | h[a+c] - h[a] * pw[c] |
次のステップ
- 発展1: 法 $2^{61}-1$ で、基数を固定した実装を破る入力を作る（差の多項式の根を狙う。格子基底簡約（LLL）で係数の小さい多項式を探す方法が知られる）
- 発展2: 2 次元ローリングハッシュ（Day039-Q3）で同じ Thue–Morse 型の攻撃が効くかを調べる
- 扱わなかった範囲: 文字列の集合を 1 つのハッシュで表す多重集合ハッシュ、Rabin–Karp の最悪計算量
検証ログ（本セッションで実行した数値）
- 正しさ（実測）: $N\le40$、2 文字（a/b）の文字列 300 ファイル × 質問 30 個（
Yesの割合 2703/9000）で、プログラム全体の出力が直接の文字列比較と全件一致 - Thue–Morse 攻撃（実測）: 奇数の基数 200 個で初めて衝突する $k$ の分布 $\{6:2,7:2,8:15,9:23,10:158\}$、最大 10（導出の $k=10$ と一致）。例2 の入力で法 $2^{64}$ は 100/100 の基数で誤答、本解は
No - 偶数の基数（実測）: 先頭 36 文字が異なり末尾 64 文字が同じ長さ 100 の組が衝突
- 法 $2^{61}-1$（実測）: $T_{17}$ と反転で 20 基数とも衝突 0
- 誕生日衝突（実測）: 相異なる 199,981 個の長さ 20 の部分文字列で、法 $10^9+7$ は 21 件（見積もり 20.0）、法 $2^{61}-1$ は 0 件
- 入力例1 の出力
Yes No Yes Yesを実行で確認 - 性能（実測）: $N=Q=2\times10^5$（2 文字のランダム文字列、$c\le1000$）で user 0.39 s、
Yes186 件 - 出所ラベル: 件数・秒数は実測（Python 3.14.7）。$v_2(B^{2^i}-1)\ge i+2$ と $\le (L-1)/p$ は導出。Thue–Morse による $2^{64}$ ハッシュ破りは競技プログラミングで広く知られる手法だが、本セッションでは初出の文献を参照していない
- 検証スクリプト: スクラッチパッドの
d161/q5.py・q5_test.py・q5_check.py