競プロ典型90問 015 Don't be too close(★6)
条件の整数の差$ kを固定して考える.
ここで, $ kに対してボールを選ぶ回数は$ \frac{N}{k}回程度であることを利用する.
すると, ボールを選ぶ回数についても調和級数の性質より全探索できる. この値を$ iとおくと, 答えに$ _{N - (k - 1)(i - 1)} C _iを加算すればよい. この組み合わせの計算は適切な帰着により導出できる.
計算量は$ O(N \log N)となる.
数え上げパートが難しい.