题解：CF2150D Attraction Theory

· · 题解

考虑对合法的序列进行刻画。

显然有 p 不降，因此考虑其桶 t。

显然 t 非 0 的值是一段区间，记为 [l,r]。则有 \forall i\in (l,r),t_i\bmod 2=1。这可以对于所有状态归纳证明得到。

关于充分性，不妨假设 l=1，则操作 t_l 次 1，t_r 次 r-l+1，再把每个 i\in (l,r) 都调对即可。

考虑计数部分，l=r 是简单的。

其余情况考虑枚举两端的奇偶性，算一下这个值为 1 或 2 时产生的贡献，再算上给每个数补若干个 2 产生的贡献。由对称性只需对于一个数，考虑剩下的数有 k 个，和为 m，由组合意义，枚举第 x 个是这个数，则剩下是插板，写出式子：

ans &= \sum_{i=1}^m \binom{m-i+k}{k} \\ &= \sum_{i=0}^m \binom{i}{k} \\ &= \binom{m+k}{k+1} \end{aligned}

最后一步是根据上指标求和得到的。

至此，时间复杂度 O(n)。