[CEOI 2016] kangaroo 大力推导

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

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

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

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

使用附加因子法，设 $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}$ 项，也就变为：

而对于特殊位置的情况，本来是 $F_i(x)=(1+x)F_{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$）：

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

答案显然还是 $H_n(0)$。

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

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

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

至于为什么是复合 $(\text e^{\text i u}-1)$ 而不是 $\text e^{\text i u}$，这是为了复合操作对形式幂级数收敛（计算 $f \circ g$ 时，要么 $f$ 是有限项的，要么 $g$ 的最低非零项至少为 $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)$ 的时间复杂度计算的。
这样一来，答案就是

$\sin u$ 和 $\cos u$ 的导数都是容易计算的，所以考虑逐项求和：

配合线性筛，即可做到 $\Theta(n)$ 的时间复杂度。