题解：AT_agc068_a [AGC068A] Circular Distance

感觉套路但是不会做。

经典的转化为 $\max\leq d$ 的计数。考虑断环成链，并钦定选择位置 $0$，最后给答案 $\times \frac{L}{n}$ 即可。

对于一对选择的位置 $l,r(r>l)$，需要满足 $r-l\leq d$ 或 $r-l\geq L-d$，意味着 $[d+1,L-d-1]$ 是不能选的。并且对于 $[0,d]$ 和 $[L-d,L)$ 内部的方案是不会矛盾的，所以考虑这两个区间之间的限制关系。

具体来说，对于一个选择的点 $x(0\leq x\leq d)$，在 $[x+d+1,L+x-d-1]$ 是不可以选的。我们把 $[0,d]$ 这一段向右平移 $d+1$ 个单位，设 $l=L-2d-2$，那么原问题变成：

在 $[d+1,L]$ 之间给每个点做选择，可以染白(选左边)、染黑(选右边)和不选，一个白点 $x$ 需要满足 $[x,x+l]$ 之内不能有黑点，要求 $d+1$ 是白点，$L$ 是黑点。

发现限制只与黑白连续段的分界点有关，枚举黑白连续段数量，可以插板求出方案数，时间复杂度 $O(\frac{L}{l})$。总时间复杂度 $O(L\ln L)$。