概要

$2^{61}-1$ mod Rolling Hash が任意の基数で落ちる（数列比較の）問題が作れた。
基数を2つとってハッシュのペアで比較するか、もっと大きいmodを使おう。

Rolling Hashとは

文字列や整数列に対するハッシュ関数の一つ。以下では整数列のみを扱う。
法 $M$ と基数 $B$ を用いたときの、数列 $s=s_0, \dots, s_{L-1}$ に対するRolling Hash $H(s; M, B)$ は次で定義される。

$\displaystyle H(s; M, B) := \sum_{i=0}^{L-1} B^{L-1-i}s_i \bmod M$

数列をいじった後のハッシュ値を、元の数列のハッシュ値からうまく計算できたりする。

衝突確率

異なる数列が同じハッシュ値をとることを、ハッシュの衝突と呼ぶ。
法 $M$ が十分大きな素数のとき、長さ $L$ の数列 $a, b$ のハッシュが衝突するような基数 $B$ は高々 $L-1$ 個しかない。

証明

$H(a; M, B) = H(b; M, B) \iff \sum_{i=0}^{L-1} B^{L-1-i}(a_i - b_i) = 0 \pmod M$

ここで法 $M$ が素数であることから剰余類 $\mathbb{Z}/M\mathbb{Z}$ は整域である。

整域上の $L-1$ 次多項式の根は高々 $L-1$ 個であることから、結論を得る。
互いに異なる数列 $s^{0}, \dots, s^{n-1}$ のどこかで衝突が起こるような基数 $B$ は高々 ${}_nC_2 (L-1)$ 個しかない。
法 $M=2^{61}-1 \approx 2.3 \times 10^{18}, n\approx 2\times10^{6}, L\approx 2\times10^{6}$ とした場合、どんな基数 $B \in \{0, M-1\}$ を取っても衝突してしまうケースがあるのではないか？ $\implies$ そのような問題が構築できた。

問題の構築

アイデア

$x^{L-1} - r^{u(L-1)} = 0 \pmod M$ は $x = r^{u}, r^{d+u}, \dots, r^{(L-2)d+u} \bmod M$ を根に持つ。
- $L-1$ が $M-1$ の約数のときに限る。
- $d := (M-1) / (L-1)$ とおいた。
- $r$ を $M$ の原始根とした。
- $u$ は任意の整数。
  
  証明
  
  $k=0,\dots, L-2$ に対して $(r^{kd+u})^{L-1} = (r^{M-1})^{k}r^{u(L-1)} = 1^{k}r^{u(L-1)} = r^{u(L-1)} \pmod M$
$B = r^{in+j+kd} \bmod M, k=0, \dots, L-2$ のとき、 $H(a^{i}; M, B) = H(b^{j}; M, B)$ となる（衝突する）。
- $a^{i} := [r^{-in(L-1)} \bmod M, 0, \dots, 0], \ 0 \le i \lt n$ とおいた。
- $b^{j} := [0, \dots, 0, r^{j(L-1)} \bmod M], \ 0 \le j \lt n$ とおいた。
  
  証明
  
  $H(a^{i}; M, B) = H(b^{j}; M, B) \iff B^{L-1} - r^{(in+j)(L-1)} = 0 \pmod M$
  
  $in+j=u$ とおけば上の議論により直ちに結論を得る。

$n^{2} \ge d$ となるように $n$ をとれば、 $in+j$ が $0, \dots, d-1$ をカバーすることで $B=r^{0}, r^{1}, \dots, r^{M-2} \bmod M$ でハッシュの衝突が生じる。 $r$ は原始根なので、これは任意の基数 $B$ で衝突が生じることを意味する。

仕上げ

$M=2^{61}-1 \approx 2.3\times10^{18}$ のとき、 $L \approx 2\times10^{6}, n \approx 2\times10^{6}$ 程度にすれば $n^{2} \ge d := (M-1)/(L-1)$ とできる。
$a^{i}, b^{j}$ をそのまま与えると、入力サイズが $4\times10^{12}$ 程度になってしまう。
$a^{i}, b^{j}$ はほとんど $0$ で埋められた数列なので、情報量は小さい。
クエリの問題にしてみる。各クエリで数列が編集されて、途中で出てきた数列の種類数を答えさせる。

完成した問題

Input: 全て整数

L, Q
k_1 v_1
...
k_Q v_Q

制約
- $0 \le L \lt 2\times10^{6}$
- $0 \le Q \lt 3\times10^{6}$
- $0 \le k_t \lt L, \quad t = 1, \dots, Q$
- $0 \le v_t \lt 2^{61}-1, \quad t = 1, \dots, Q$
Output
- 長さ $L$ の数列 $s^{0} := [0, \dots, 0$ ] を定義する。
- 数列 $s^{t-1}$ の $k_t$ 番目の要素を $v_t$ で置き換えた数列を $s^{t}$ とおく。
- 数列 $s^{0}, \dots, s^{Q}$ は全部で何種類あるかを出力せよ。