AGC049D Convex Sequence

发表于 分类于 ， ， 阅读次数：

题意：求 元组 的方案数，满足 :

答案对 取模，，时限 。

不难发现，第二条等价于要求这个序列非严格下凸。（题目名也明示这一点）

看到凸性，可以想到充要条件：一阶差分单调递增，即二阶差分全正。

设 为 的二阶差分， 为一阶差分初始值，则有 其中， 必须是非负的，但是 可能是负的。

不难发现，若枚举 ，则相当于枚举 ，显然是没有出路的。

而且，这些变量的系数很大，做背包也不方便。

总的来说，差分将变量之间的联系割裂，将非负的不等式性质破坏了，所以复杂度就没有依靠。

我们考虑一些非代数的做法。

不难发现，函数中一旦出现 ，此后就至少是 ，这样不会超过 轮。

所以， 只有两侧有小的凸起，中间都是 。

我们考虑左侧突起的结束位置，即第一个最小值的位置，设为 。

满足要求的凸函数可以这样构造：

初始时是全 序列。

  • ① 将所有位置的值

  • ② 对于 左侧的数，将一个长度为 的前缀 。

  • ③ 对于 右侧侧的数，将一个长度为 的后缀 。

任意地执行上述三个操作。

为了保证 是第一个最小值，至少要对前缀 操作一次。

不难证明构造出的是一个下凸数组。

对于一个下凸数组，也能根据其二阶差分和最小值来还原出操作序列。

现在只需要考虑这些操作对和的影响，跑背包就好了。

当 逐渐增大时，会逐渐加入 ② 操作，减少 ③ 操作。还有一个强制的 ② 操作。

这些都可以用完全背包和 背包以及其反演 完成。

由前面的结论，，所以复杂度就是 。