Luogu7482 不条理狂诗曲

题意：给出一个长度为 的非负整数序列 ，记 为 中选出若干不相邻元素的和的最大值。

求下列式子的值。

答案可能较大，对 取模。

，时限 。

---

考虑分治，每次计算跨越分界线 的所有区间的贡献。记

• 表示 中出若干不相邻元素的最大和。

• 表示 中出若干不相邻元素的最大和。

• 表示 中出若干不相邻元素的最大和。

• 表示 中出若干不相邻元素的最大和。

都容易用 DP 线性求出。

此时可以求单个 ：

写出跨越分界线 的所有区间的贡献：

对每个 分别计算。对 的决策进行分类讨论。

于是，将 按照 排序，满足 的就是一个前缀，可以二分得出。

贡献用前缀和计算。

复杂度 。