心跳 题解

· · 题解

很多内容和兔子想的一样, 不过自认为对"每个序列只对应了唯一的单调栈大小"这一点的证明比较趣味, 所以还是把写的东西挂出来了.

我们首先考虑 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, 也就是

\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},

进而

x^2+x-1\right)}.

我们最后的答案则是

\frac{A-B}{t} +B,

它的 x^nt^m 次项表示的是序列中出现的最小的数为 m 的序列数量.

我们用上述的有理分式直接递推, 就可以在 O(n^2) 时间内计算出答案了.

把上面提到的有理分式做分式分解, 就可以在 O(n) 甚至 O(\sqrt n\log n) 时间内计算出答案了.