Again Counting Stars 糖糖做法

· · 个人记录

前面的转化不说了，现在要解决的问题如下：

给出单调不增数组 s_1, \ldots, s_{n-1}，你需要对每个 1 \leq p \leq n 计数有多少个数组 b'_1, \ldots, b'_{n-1} 满足：

这里和官方题解是完全反着的，相当于做的是后缀和而不是前缀和。

然后把序列 reverse，相当于 s 和 b' 都是单调不降的。

这个时候就相当于要对于每个 i 计算 b'_i 是第一个 b'>s 的位置的方案数，以及 b'_i 是最后一个 b'>s 的位置的方案数。称前者为 A_i，后者为 B_i。

我们考虑暴力 dp 是怎么做的，相当于记录 f_{i,j} 表示 b'_i=j 的方案数，然后转移是先做前缀和再删掉一个前缀。

我们熟知对多项式求前缀和还是多项式，但是删掉一个前缀的处理比较烦。

于是考虑不要求不合法的位置是 0，只保证合法的位置的值是对的。

此时相当于 F(i) 变成 F 在 l\sim i 的前缀和，l 是没被删的最小位置。

可以看出 F 显然是多项式，于是直接维护连续点值拉插可以做到 O(n^2) 求一个 A_i 以及 i 作为起点对每个 B_j 的贡献。

于是求一个 B_i 相当于对所有 j 求它们作为起点的贡献和，相当于维护 F 之后多一个加入 s_i 这个新起点的转移，也就是全局 +1。

于是求所有 B_i 可以做到 O(n^2)，而求所有 A_i 就直接把做法转置就好了。

这样我们可以跑出最优解 7 倍的时间。