AtCoder Regular Contest 120 F Wine Thief-526互联

Hint

如果是一个环怎么做？

Answer

由于是一个环，因此环上每个点对最终答案造成的贡献都相同。设 $f_{i,j}$ 为长度为 $i$ 的序列选 $j$ 个不相邻的点的方案数，则 $f_{i,j} = \binom{i-j+1}{j}$。应该很好理解，考虑一个长度为 $i-j+1$ 的链，链头、链尾和两个数之间都可以插入一个元素，总共需要插入 $j$ 个，因此方案数是 $\binom{i-j+1}{j}$。每个点对答案的贡献为 $a_i \times f_{n-3,k-1}$（就是钦定这个点不选，断环为链）。

这启发我们在环的基础上考虑。发现除了环的答案，链的要多考虑两端都选的方案。设 $g_{i,j,k}$ 为在 $[i,j]$ 的链选 $k$ 个不相邻的点的答案。令 $len = j - i + 1$，那么：

\[g_{i,j,k} = f_{len-3,k-1} \times (\sum\limits_{p=i}^j a_p) + f_{len-4,k-2} \times (a_i + a_j) + g_{i+2,j-2,k-2} \]

第一部分是环的答案，后面是钦定选 $a_i,a_j$，$[i+2,j-2]$ 选点的方案为 $f_{len-4,k-2}$，作为系数乘上 $a_i + a_j$，最后再递归下去。

时间复杂度 $O(n)$。