問題

長さが一様とは限らない $N$ 個の有限長の整数列 $A_0, A_1, \dots, A _ {N - 1}$ が与えられる。 短い側を循環的に拡張した数列の各点の積の総和 \(A \star B = \sum _ {i = 0} ^ {\max(|A|, |B|) - 1} A _ {i \bmod |A|} \cdot B _ {i \bmod |B|}\) を考える。 $A_x \star A_y$ を求めよという形のクエリが $Q$ 個与えられるので答えよ。

考察

  1. 愚直だと $O(Q \max A_i )$ ぐらい
  2. $\sum A_i \le 2 \times 10 ^5$ の制約があるのでメモ化すると落ちる？
  3. 数列 $A$ と正整数 $k$ に対し長さ $k$ の数列 $B = (A_0 + A_k + \dots, A_1 + A _ {k + 1} + \dots, \dots, A _ {k - 1} + A _ {2k - 1} + \dots)$ を前計算しておくとどうか
  4. 一見して調和級数の和になって計算量が落ちそうに見えるけどだめで $O( A ^2)$
  5. (やれば実は上手く行くかもだけど解説見る)

解法

$S = \sum |A_i|$ とおく。 数列を長さが $\sqrt{S}$ 以下かどうかで分割すると $O(Q \sqrt{S} + S \sqrt{S})$ で解ける。

各数列 $A$ と正整数 $k \le \sqrt{S}$ に対し長さ $k$ の数列 $B = (A_0 + A_k + \dots, A_1 + A _ {k + 1} + \dots, \dots, A _ {k - 1} + A _ {2k - 1} + \dots)$ を前計算しておく。 すると長さ $\sqrt{S}$ 以下の数列を含むクエリに対しては $O(\sqrt{S})$ となり、全体でも $O(Q \sqrt{S})$ で抑えられる。

どちらも長さ $\sqrt{S}$ 超過の数列に関するクエリについては遅いが、実は間に合う。 そのようなクエリがすべて与えられるとしよう。 メモ化すれば重複がないとしてよい。 長さ $\sqrt{S}$ 超過の数列は高々 $\sqrt{S}$ 個しかない。 数列 $A_i$ のある文字に注目したとき、それが用いられるのは $j \ne i$ な数列 $A_j$ ごとに $1$ 回であるのでつまり $\sqrt{S}$ 回。 すべての数列のすべての文字を考えれば $S$ 個なので、全体で $O(S \sqrt{S})$ かかることになるが、これは間に合う。

反省

  • 調和級数の和が $H_n \approx \log n + \gamma$ なのちゃんと認識してなかった (結局不要だったけど)
  • $\sqrt{S}$ 超過の数列の計算量は解説を見ないと分からなかった

リンク