[CEOI 2016] kangaroo 大力推导

· · 题解

容斥做法太神秘了，看不懂怎么办？爆推式子一样能做！

不失一般性，我们可以设 s<t。若非如此，直接将二者交换即可。
我们从朴素的递推式做推导：

f_{i,j}=\begin{cases} j f_{i-1,j+1}+(j-[i>s]-[i>t])f_{i-1,j-1} \ , \ i \neq s \wedge i \neq t \\ f_{i-1,j}+f_{i-1,j-1} \ , \ \text{otherwise}\end{cases}

边界值为 f_{1,1}=1，答案为 f_{n,1}。

按行建立生成函数，则在 i \neq s \wedge i \neq t 时，递推可以写为

F_i(x)=(1+x^2)F_{i-1}'(x)+((1-[i>s]-[i>t])x-1/x)F_{i-1}(x)

使用附加因子法，设 F_i(x)=p_i(x)G_i(x)，则当 p_i(x)=x(1+x^2)^{([i>s]+[i>t]-2)/2} 时，G_i 的递推中刚好消去含 G_{i-1} 项，也就变为：

G_i(x)=(1+x^2)G_{i-1}'(x) \ \ (i \neq s \wedge i \neq t)

而对于特殊位置的情况，本来是 F_i(x)=(1+x)F_{i-1}(x)，在新的递推式中为

G_i(x)=(1+x)(1+x^2)^{-1/2}G_{i-1}(x)

显然边界值为 G_1(x)=1+x^2，答案为 G_n(0)。

现在考虑做基变换换元，设 H_i(u) = G_i(x)，则有（i \neq s \wedge i \neq t）：

H_i(u)=\frac{\text d H_{i-1}(u)}{\text du}=\frac{\text d H_{i-1}(u)}{\text dx} \frac{\text dx}{\text du}

不难看出现在得到微分方程 u'=1/(1+x^2)，即 u=\arctan x。那么就能得到 H_1(u)=(\cos u)^{-2}，以及递推：

H_i(u) = \begin{cases} (\sin u +\cos u)H_{i-1}(u) \ , \ i = s \vee i = t \\ \text d H_{i-1}(u)/\text du \ , \ \text{otherwise}\end{cases}

答案显然还是 H_n(0)。

按递推式可以反推出 H_0(u)=\tan u，再设 A=s-1,B=t-s-1,C=n-t。

现在也就可以将答案表示为

C![u^C](\sin u+\cos u)\left(\frac{\text d^B}{\text du^B}(\sin u+\cos u)\frac{\text d^A(\tan u)}{\text d u^A}\right)

现在就得到了一个 \Theta(n \log n) 的做法，要进一步优化，可以考虑：

\tan u=-\text i\frac{\text e^{\text i u}-\text e^{-\text i u}}{\text e^{\text i u}+\text e^{-\text i u}}=-\text i \frac{(u+1)-(u+1)^{-1}}{(u+1)+(u+1)^{-1}}\circ (\text e^{\text i u}-1)

至于为什么是复合 (\text e^{\text i u}-1) 而不是 \text e^{\text i u}，这是为了复合操作对形式幂级数收敛（计算 f \circ g 时，要么 f 是有限项的，要么 g 的最低非零项至少为 1 次）。

在计算中我们系数保留到 {} \bmod u^n 肯定就足够了。可以设

W(u)= -\text i \frac{(u+1)-(u+1)^{-1}}{(u+1)+(u+1)^{-1}} \bmod u^n

则有 W(\text e^{\text iu}-1)\equiv \tan u \pmod{u^n}。

现在只需要再设 \hat W(u)=W(u-1)，就能得到 \hat W(\text e^{\text iu})\equiv \tan u \pmod{u^n} 了。而 \hat W(u) 是可以用整式递推以 \Theta(n) 的时间复杂度计算的。
这样一来，答案就是

C![u^C](\sin u+\cos u)\left(\frac{\text d^B}{\text du^B}(\sin u+\cos u) \sum_{k=0}^{n-1} \hat w_k (\text i k)^A \text e^{\text i k u}\right) $$C!\sum_{k=0}^{n-1} \hat w_k( \text i k)^A[u^C](\sin u+\cos u)\frac{\text d^B}{\text du}\left( \frac{\text e^{\text i(k+1)u}-\text e^{\text i (k-1)u}}{2\text i}+\frac{\text e^{\text i (k+1)u}+\text e^{\text i (k-1)u}}{2}\right)$$ $$=\frac 12C!\sum_{k=0}^{n-1} \hat w_k( \text i k)^A[u^C](\sin u+\cos u)((k+1)^B(1-\text i)\text e^{\text i (k+1)u}+(k-1)^B (1+\text i)\text e^{\text i (k-1)u})\text i^B$$ $$=\frac{\text i^{A+B}}{4}C!\sum_{k=0}^{n-1} \hat w_k k^A [u^C] ((1-\text i)\text e^{\text i u}+(1+\text i)\text e^{-\text i u})((k+1)^B(1-\text i)\text e^{\text i (k+1)u}+(k-1)^B (1+\text i)\text e^{\text i (k-1)u})$$ $$=\frac{\text i^{A+B+C}}{4}\sum_{k=0}^{n-1} \hat w_k k^A\left((k+1)^B(1-\text i)((1-\text i) (k+2)^C+(1+\text i)k^C) +(k-1)^B(1+\text i)((1-\text i) k^C+(1+\text i)(k-2)^C)\right)$$ 配合线性筛，即可做到 $\Theta(n)$ 的时间复杂度。