困ったときの平方分割。
問題概要
考えたこと
要素の総和が $ k $ の"素晴らしい整数列"の個数を $ f (k) $ とする。
また、このうち最後の要素が $ x $ であるものの個数を $ f _ x (k) $ とすると、
$$ f _ x (k + x) = f(k) - f _ x (k) $$
が成り立つ。
右辺にある $ f _ x (k) $ に (1) を代入し続けると、$ t = \lfloor \frac {k} {x} \rfloor $ として、
$$ \begin{align} f _ x (k + x) & = f (k) - f (k - x) + f (k - 2x) - f (k - 3x) + \cdots \notag \\ & \qquad \cdots + (-1) ^ t ( f (k - tx) - f _ x (k - tx) ) \notag \\ & = \sum _ { i = 0 } ^ t (-1) ^ i f (k - ix) - (-1) ^ t f _ x (k - tx) \notag \end{align} $$
ここで、$ f _ x (k) = 0 \, ( x > k ) $ であるから、
$$ \begin{align} f _ x (k + x) = \sum _ { i = 0 } ^ t (-1) ^ i f (k - ix) \notag \\ \Leftrightarrow f _ x (k) = \sum _ { i = 1 } ^ t (-1) ^ { i - 1 } f (k - ix) \end{align} $$
である。
(2) の右辺は $ k $ を昇順に見ていく際に各 $ x $ に対して $ k \bmod x $ の値によって管理することができるため、$ f _ x (k) $ の計算は $ O(1) $ で済む。
これを求めていけば最終的に $ f (N) $ が得られるが、愚直にやると時間計算量、空間計算量ともに $ O ( N ^ 2 ) $ であるから $ N \leqq 2e5 $ の制約においては厳しい。
これは平方分割の要領で解決できる。
具体的には、$ x > \sqrt N $ において $ f _ x (k) $ の総和を求めることを考えると、(2) の右辺は $ i $ の値によってもまとめることができて、各 $ i $ に対して $ k \bmod i $ の値で管理すればよい。
計算量は $ O ( N \sqrt N ) $ となる。
なお、出力する値は個数ではなく長さなので、同様に計算すること（省略）。
