D - Range Add Query Editorial by maspy
K の上限がない場合の解法制約に \(K\) の上限がない場合にも適用できる、\(O(N+Q)\) 時間で解ける解法を紹介します。
[注]
ABC コンテスト D 問題で要求される通常のレベルを超える解法となります。(F~G 問題のレベルになるのかなと思います。)
\(K\leq 10\) の場合の解法を理解していることを前提とします。
[解法]
次のアルゴリズムにより、解くことができます.
- \(p\) を十分大きな素数(後述)として、整数 \(x_1, \ldots, x_{K-1}\) を一様ランダムにとる。\(x_0 = -(x_1 + \cdots + x_{K-1})\) とする。
- \(A_i' = A_i\cdot x_{(i\bmod K)}\) とする
- \(\sum_{L\leq i\leq R} A_i' \equiv 0\pmod{p}\) であるか否かに従って
Yes
あるいはNo
と出力する。
\(A_i'\) の累積和を前計算しておくことで、本問題は時間計算量 \(O(N+Q)\) 時間で解くことができます。
[解法の正当性]
以下では、次を確かめます。
- 真の解が
Yes
ならば、上のアルゴリズムはYes
を出力する。 - 真の解が
No
ならば、上のアルゴリズムは確率 \(1-1/p\) でNo
を出力する。
以下では区間 \([L,R]\) をひとつ固定して論じます。単に \(\sum_{i}\) などと書けば、\(i\) は \([L,R]\) 内を動くものとします。
\(0\leq k < K\) に対して次のように \(a_k\) を定めます:
- \(a_k = \sum_{i\equiv k \pmod{K}} A_i\)
判定すべきは \(a_0 = \cdots = a_{K-1}\) であるか否かです.\(1\leq k < K\) に対して \(b_k = a_k - a_0\) とおけば、これは \(b_1 = \cdots = b_{K-1} = 0\) と同値です。
\(p\) が十分大きな素数であるとき、これは \(b_1 \equiv \cdots \equiv b_{K-1} \equiv 0\pmod{p}\) と同値です。具体的には本問の制約のもと \(|b_k| \leq 10^9\cdot (2\cdot 10^5)\) となるので、\(p\) を \(2\cdot 10^{14}\) より大きくとればよいです(\(10^9\) 程度の素数を複数使う解法で代用することも現実的な選択肢です)。
\[\sum A_i' = \sum_{k=0}^{K-1} a_kx_k = \sum_{k=1}^{K-1}b_kx_k\]
なので、残りの主張を示すには次の \(2\) つのことを確かめればよいです。
- \(b_1 \equiv \cdots \equiv b_{K-1} \equiv 0\pmod{p}\) ならば、必ず \(\sum_k b_kx_k \equiv 0\pmod{p}\) となる。
- \(b_1 \equiv \cdots \equiv b_{K-1} \equiv 0\pmod{p}\) でないならば、確率 \(1-1/p\) で、\(\sum_k b_kx_k \not\equiv 0\pmod{p}\) となる。
前者の主張は自明です.後者の主張は \(b_m \not\equiv 0\pmod{p}\) となる \(b_m\) をとると、\(x_1,\ldots,x_{K-1}\) のうちで \(x_m\) 以外を固定したとき、反例となる \(x_m\) が一意であることから分かります。
なお、後者の主張の一般化として Schwartz–Zippel lemma がよくハッシュの衝突確率の解析に用いられます。
[補足]
\(p = 998244353\) や \(p = 1000000007\) などの「十分大き」くはない単一の \(p\) を使う解法だと、\(x_1, \ldots, x_{K-1}\) を乱択したとしても WA
となるテストケースを作ることができます。例えばすべての \(i\) に対して \(A_i \in \{-998244353, 0, 998244353\}\) であるような長い数列が \(p = 998244353\) に対する簡単なハックケースとなります。
AtCoder (事前に用意されたテストケースを攻略できれば正当となる)の場合では、作問準備者がわざわざそのような解法を想定して対策テストケースを作成していなければ十分高い確率で AC
できます。
posted:
last update: