题目大意
对某个奇怪东西计数。
分析
非常经典的环形计数。
不难观察得到，需要计数的结构是一个分组，并且不需要对旋转进行去重。
考虑 DP，假设 $1$ 和 $n$ 不在一个分组，考虑设状态 $f_i$ 为对 $1$ 到 $i$ 进行分组的方案数，那么递推式有
$$ f_j = \sum_{i=0}^{j - 1} f_i \times (j - i) = \sum_{i=0}^{j-1} \sum_{k=0}^j f_k $$
乘 $j-i$ 的原因是最后一个分组的长度是 $j-i$，其每个元素都有可能和中心连线。
接下来考虑 $1$ 和 $n$ 在同一个分组的情况，假设 $1$ 和末尾 $i$ 个元素同一个分组，因此
$$ g_i = \sum_{j=i}^{n} f_{n-j} \times j $$
全体求和即为
$$ h_n = \sum_{i=1}^n g_i = \sum_{j=1}^{n-1} f_{n-j} \times j^2 $$
可以得到 $h$ 的 OGF
$$ h(x) = \frac{x+x^2}{(1-3x+1)(1-x)} $$
不难还原出递推式。
全部代码请看：Luogu/2x/P2144.cpp。