CF1738E Balance Addicts

个人思路：

\(sum_i\) 表示前 \(i\) 个数的前缀和，推一下式子可知是要选若干对 \(l_i,r_i\)，使得 \(l_1 < l_2 <\dots < l_k \le r_k < \dots < r_2 < r_1\) 且 \(sum_{l_i} + sum_{r_i} = sum_n\times 2\)。

然后就不会做了。

正解：

\(pre_i\) 表示 \([1,i]\) 的和，\(suf_i\) 表示 \([i+1,n]\) 的和，题目等价于选若干对 \(l_i,r_i\)，使得 \(l_1 < l_2 <\dots < l_k \le r_k < \dots < r_2 < r_1\) 且 \(pre_{l_i} = suf_{r_i}\)。

上面的做法遗漏了 \(a_i \le 0\)，所以 \(pre_i\) 和 \(suf_i\) 分别为从左往右单增和从右往左单增，不同的值成独立段。

显然，对于一个段 \([l_l, l_r]\) 和 \([r_l, r_r]\)，枚举选的对数 \(p\)，贡献为 \(\sum\limits_{0 \le p \le min(l_r-l_l+1, r_r-r_l+1)} C_{l_r-l_l+1}^p \cdot C_{r_r-r_l+1}^p\)。

所有段贡献的乘积即为答案。

但是如果 \([l_l, l_r]\) 与 \([r_l, r_r]\) 重合，需要特判。发现此时任选位置切割，一定满足回文，贡献为 \(2^{l_r - l_l + 1}\)。

时间复杂度 \(\Theta(n)\)

巴特西

CF1738E Balance Addicts

最新文章

热门文章