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)\)。
标签:AtCoder,Contest,传送门,Thief,len,times,答案 From: https://www.cnblogs.com/zltzlt-blog/p/17357174.html