心跳 题解

Elegia

2023-01-22 16:39:58

Solution

很多内容和兔子想的一样, 不过自认为对"每个序列只对应了唯一的单调栈大小"这一点的证明比较趣味, 所以还是把写的东西挂出来了. ----- 我们首先考虑 $m=1$ 的子任务如何解决. 这个时候, 我们其实就是希望知道有多少可构造的序列 $a$. 序列 $a$ 首先看起来和 $f(p)$ 本身的值 (也即不去掉任何一个数时候的单调栈大小) 有着莫大的关系. 我们假设 $f(p)=l$, 首先, 计数所有的二元组 $\langle \{a\}, l \rangle$ 看起来是更简单的. 这里的意思是, 我们先对于每个 $l$ 把能构造出的 $\{a\}$ 的数量数出来, 这样显然是不漏的. 一个让人安心的事实是, 这样的数法实际上也是不重的, 通过打表可以发现每个可构造的序列 $\{a\}$ 只会对应于一个 $l$. 当然, 通过接下来对结构的讨论, 我们也会严谨地确认这一点. 对于所有不在单调栈上的位置 $i$, 我们发现删去它不会影响单调栈, 也就是必然有 $f(P_i) = l$. 对于那些在单调栈上的位置 $i$ 呢? 最坏情况, 就是到单调栈下一个元素之前没有任何数被加了进去, 这样的话就是 $f(P_i)=l-1$ 了. 而最好的情况则是到下一个元素之前刚好是全都可以加入的, 也就是说, 如果之间有 $d$ 个数, 那么最好情况就有 $f(P_i)=l-1+d$. 为什么这些之间的数都能达到呢? 一个比较直接的看法是注意到, 我们只关心排列的大小关系, 这实际上和 $n$ 个实数的大小关系是一样的, 所以我们可以随便插在我们需要的大小. 这个说法准确吗? 不完全. 特例是 $i=1$ 的情况. 如果 $d\geq 1$, 我们发现删去 $p_1$ 之后, 是一定会多出来至少一个单调栈里的元素的, 对于单调栈后面的则没有这个问题, 因为可以让暴露出来的值全都小于之前单调栈里的数. 接下来, 我们就得到了和 $l$ 有关的可构造序列的一个"精确"的刻画: > 对于下标 $1=q_1 < q_2 <\dots < q_l < q_{l+1}=n+1$, 如果限制排列 $p$ 的单调栈的下标恰为 $q_1,\dots,q_l$, 那么这些排列给出的可构造的 $\{a\}$ 由如下笛卡尔积规则生成, 我们设 $d_i = q_{i+1} - q_i - 1$: > - 对于 $j\neq q_i$ (不在单调栈上的数), 一定有 $a_j = l$. > - 对于 $j = q_1 =1$, 如果 $d_1=0$, 那么 $a_1 = l-1$, 否则 $l\leq a_1\leq l - 1 + d_1$. > - 对于 $i > 1$ 的 $j=q_i$, 有 $l-1\leq a_{j} \leq l-1+d_i$. 接下来我们看看为什么同一个 $a$ 不会对应于两个 $l$. 考虑 $\sum (a_i-l)$ 的值域范围, 这就是 $-\sum 1 = -l$ 到 $\sum (d-1) = n - 2l$. 也就是说, $\sum a_i$ 的值域区间是 $[L_l, R_l] = [nl-l, nl+n-2l]$. 那么, 我们发现, $L_{l+1} - R_l = l-1$, 所以 $l>1$ 的区间是互不相交的, 而 $l=1$ 和 $l=2$ 之间唯一的交点是 $\sum a_i = 2n-2$, 这个情况在 $l=1$ 时候只能形如 $\{a\} = n-1,1,1,\dots,1$, 在 $n\geq3$ 的时候是不可能有 $l=2$ 的对应构造的. 这就说明了前文提到的, 可以通过打表验证的事实. 我们现在已经成功地给出了一个初步的刻画, 但是它距离我们想要进行计数, 还有些要注意的事项. 刚刚这个刻画所不足的地方在于, 不同的一组单调栈下标是有可能给出相同的序列的, 因为我们可以以一定的自由度重排那些明明满足 $a_i=l$ 却还在单调栈上的数. 为此, 我们可以考虑把 $l$ 的地位看淡. 转而考虑序列 $b_i = a_i - l$. 我们此时关心的是, 这样一个序列 $\{b\}$ 可以对应于多少个 $l$. 这样一来, 首先 $b_i\neq 0$ 的必须在单调栈上, 但还有一个要考虑的就是 $b_1$ 的问题. 根据前面的刻画, 如果 $b_1 =-1$, 那此时就算 $b_2 =0$, 也必须让 $2$ 在单调栈中. 接下来对于一个大小为 $D$ 的间隔, 如果对应单调栈位置的 $b_i=d-1$, 那么我们可以利用这段区间插入尽量多的 $b_i=0$ 的单调栈, 其需要长度至少是 $2$, 因此这一段可以插至多 $\lfloor (D-d)/2\rfloor$ 个. 对于 $m=1$ 的情况, 我们不需要考虑 $a_i$ 的下界, 此时只需对每个可构造的 $\{b\}$ 序列, 设其能最多按照上面的方法插 $r$ 个 $b_i=0$ 的单调栈, 那么对答案的贡献是 $r+1$. 我们先来尝试写出 $m=1$ 情况的生成函数. 除去单调栈里的第一个元素, 剩下每段的转移是一样的, 我们需要避免 $d=1$ 的情况 (因为这对应 $b_i=0$), 设 $x$ 计量段的长度, $y$ 计量可以额外插的数量, 那么一段的贡献是 $$ P(x, y) = \sum_{d\neq 1, D} x^{D+1}y^{\lfloor(D-d)/2\rfloor} = \frac{x(1+x)}{(1-x^2y)(1-x)} - \frac{x^2(1+x)}{1-x^2y}. $$ 对于第一段, 我们按照 $b_1 = -1$ 与否分成两类讨论, 不过它们贡献都是一样的, 总贡献是 $$ Q(x, y) = \frac{2x^2(1+x)}{(1-x^2y)(1-x)}. $$ 因此生成函数是 $$ F(x, y) = \frac{Q}{1-P} = -\frac{2 x^2 (x+1)}{x^4-x^3 y+x^2 y+2 x-1}. $$ 我们关心的是 $$ F(x, 1) + \frac{\partial F}{\partial y}(x,1) = -\frac{2 x^2 (x+1) \left(x^4+2 x-1\right)}{\left(x^4-x^3+x^2+2 x-1\right)^2}. $$ 所以, $m=1$ 的情况可以直接通过计算这个线性递推得到. 对于一般的 $m$, 我们需要考虑扩充我们记录的东西. 首先要记录我们总共用的段数, 此外, 还需要考虑是否存在 $b_i=-1$. 我们先假设存在 $-1$, 之后再容斥掉从来没出现过 $-1$ 的情况. 用 $t$ 计量段数. 我们只需令新的 $P$ 是原先的 $tP(x,y)$. 而 $Q$ 则是 $$ Q(x, y, t) = \frac{t(1+t)x^2(1+x)}{(1-x^2y)(1-x)}. $$ 得到 $$ F(x, y, t) = \frac{Q}{1-P} = -\frac{t (t+1) x^2 (x+1)}{t x^4+t x-x^3 y+x^2 y+x-1}. $$ 然后我们要把 $y^r$ 转换成 $1 + t + \cdots + t^r$, 也就是 $$ A = \frac{tF(x,t,t) - F(x,1,t)}{t-1} = -\frac{t (t+1) x^2 \left(t x^4+t x+x-1\right)}{\left(t x^3-(t+1) x^2+(t+2) x-1\right) \left(t x^4-t x^3+t x^2+t x+x-1\right)}. $$ 然后考虑不存在 $-1$ 的, 我们有 $$P(x, y, t) = t\sum_{d\geq 2, D} x^{D+1}y^{\lfloor(D-d)/2\rfloor} = \frac{tx^3(1+x)}{(1-x^2y)(1-x)}, $$ 以及 $$ Q(x, y, t) = \frac{tx^2(1+x)}{(1-x^2y)(1-x)}. $$ 进而 $$ F = \frac{Q}{1-P} = -\frac{t x^2 (x+1)}{t x^4+x^3 (t-y)+x^2 y+x-1}, $$ 进而 $$ B = \frac{tF(x,t,t) - F(x,1,t)}{t-1} =-\frac{t x^2 \left(t x^4+t x^3+x-1\right)}{\left(t x^3-x^2+2 x-1\right) \left(t x^4+t x^2+x-1\right)}. $$ 我们最后的答案则是 $$ \frac{A-B}{t} +B, $$ 它的 $x^nt^m$ 次项表示的是序列中出现的最小的数为 $m$ 的序列数量. 我们用上述的有理分式直接递推, 就可以在 $O(n^2)$ 时间内计算出答案了. 把上面提到的有理分式做分式分解, 就可以在 $O(n)$ 甚至 $O(\sqrt n\log n)$ 时间内计算出答案了.