CEOI2016 Kangaroo 线性做法

· · 题解

提供一个线性做法。

容斥信息应该是

\begin{aligned} &\quad\; \prod_{i=1}^{n-2} ([p_i<p_{i+1}](1-[p_{i+1}<p_{i+2}])+(1-[p_i<p_{i+1}])[p_{i+1}<p_{i+2}])\\ &= \prod_{i=1}^{n-2} ([p_i<p_{i+1}]+[p_{i+1}<p_{i+2}]-2[p_i<p_{i+1}][p_{i+1}<p_{i+2}]) \end{aligned}

我们自然要考虑这样一个展开式如何划分出极长的 < 段。注意到开头和结尾两段较为特殊，于是设 F, G 表示序列中间的某一段 [l, r]，没有钦定 p_{l-1}<p_l，钦定了 p_l<p_{l+1}<\dots<p_r，是否钦定 p_r<p_{r+1} 的关于长度的 GF；F^\ast, G^\ast 表示在开头。可得方程

\begin{cases} F(x) = x^2 + x F(x) + x G(x) \\ G(x) = -x^2 - 2 x F(x) - x G(x) \\ F^\ast(x) = x + x F^\ast(x) + x G^\ast(x) \\ G^\ast(x) = -2 x F^\ast(x) - x G^\ast(x) \end{cases}

可以解得

\begin{cases} F(x) = \frac{x^2}{1+x^2} = \sum_{k\ge 1} (-1)^{k-1} x^{2k} \\ F^\ast(x) = \frac{x(1+x)}{1+x^2} = \sum_{k\ge 1} (-1)^{k-1} (x^{2k-1}+x^{2k}) \end{cases}

因此容斥应该就是用两个 F^\ast(x) 和任意个 F(x) 拼接。注意到我们可以取 s>t，从而可以忽略仅有一段的情况。

从而我们将所有数划分为 [1, t-1], [t+1, s-1], [s+1, n]，取 a = t-1, b = s-t-1, c = n-s，用 x,y,z 分别计量三种数。
于是 F^\ast(x) 会变成

\sum_{k\ge 0} (-1)^k \left(\frac{x^{2k}}{(2k)!}+\frac{x^{2k+1}}{(2k+1)!}\right) = \frac12\left[(1-i)\mathrm e^{ix} + (1+i)\mathrm e^{-ix}\right]

和 \frac12\left[(1-i)\mathrm e^{iz} + (1+i)\mathrm e^{-iz}\right]。F(x) 会变成

\sum_{k\ge 1} (-1)^{k-1} \sum_{u+v+w=2k} \frac{x^uy^vz^w}{u!v!w!} = 1-\frac12\left[\mathrm e^{i(x+y+z)}+\mathrm e^{-i(x+y+z)}\right]

即需要计算

\frac14\left[\frac{x^ay^bz^c}{a!b!c!}\right]\left[(1-i)\mathrm e^{ix} + (1+i)\mathrm e^{-ix}\right]\left[(1-i)\mathrm e^{iz} + (1+i)\mathrm e^{-iz}\right] \frac1{\frac12\left[\mathrm e^{i(x+y+z)}+\mathrm e^{-i(x+y+z)}\right]}

由于 a+b+c=n-2，根据载谭 Binomial Sum 的经验，我们首先要计算

\begin{aligned} f(w) &= \frac1{\frac12[(1+w)+(1+w)^{-1}]} \bmod w^{n-1} \\ &= \frac{1+w}{1+w+\frac{w^2}2} \bmod w^{n-1} \\ &= -w f(w) - \frac{w^2}2 f(w) + 1 + w + \Delta_0 w^{n-1} + \Delta_1 w^n \\ &= \frac{1 + w + \Delta_0 w^{n-1} + \Delta_1 w^n}{1+w+\frac{w^2}2} \end{aligned}

从而我们只需要求出

f(w-1) = \frac{2(w + \Delta_0 (w-1)^{n-1} + \Delta_1 (w-1)^n)}{1+w^2}

的各项系数。记 u_j = [w^j] f(w-1)，答案就是

\frac14\sum_{j=0}^{n-2} u_j \left[\frac{x^ay^bz^c}{a!b!c!}\right]\left[(1-i)\mathrm e^{ix} + (1+i)\mathrm e^{-ix}\right]\left[(1-i)\mathrm e^{iz} + (1+i)\mathrm e^{-iz}\right] \mathrm e^{j\cdot i(x+y+z)}

另外注意到答案显然没有虚部，可以减少一些无用运算。

时间复杂度 O(n)。