制約に \(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 できます。