分式不递推

· · 算法·理论

谁家小孩算数草稿投专栏推荐了啊。

[x^b]\frac{1}{(1-x)^{a}(p-x)}

请在 O(a) 的时间求出来？知道你会 ODE，但是你先别急。

考虑分式分解。希望原式可以以如下的方式表达：

\frac{A}{(1-x)^a}+\frac{B}{p-x}

其中 A,B 是两个关于 x 的多项式。

通分一下：

B(1-x)^{a}+(-A)(x-p)=1

注意到这两个多项式在 p\neq 1 时是互质的，可以做 exgcd。做多项式带余除法：

(1-x)^a=C(x-p)+(1-p)^a

取 X_0=0,Y_0=(1-p)^{-a}，带回原式：

X=(1-p)^{-a},Y=-C(1-p)^{-a}

也就是，A=C(1-p)^{-a},B=(1-p)^{-a}。

$$x_1^{a}=(1-p)^a-(1-p-x_1)\sum_{i=0}^{a-1}(1-p)^{a-1-i}x_1^{i}$$ 因此 $$C=-\sum_{i=0}^{a-1}(1-p)^{a-1-i}(1-x)^{i}$$ 所以答案等于： $$(1-p)^{-a}(p^{-b-1}-\sum_{i=0}^{a-1}(1-p)^{i}\binom{b+i}{i})$$ 扩展一下，一次多项式 $p-x$ 变为了二次，一个想法是分式分解。根据两个根的共轭性，只需要求一个线性递推。 设二次方程的两个根 $\lambda_1,\lambda_2$ 是共轭的，要求出 $[x^b]\frac{1}{(1-x)^a(\lambda_1-x)(\lambda_2-x)}$。 把二次分式分解开，相当于 $\frac{1}{(\lambda_2-\lambda_1)(\lambda_1-x)}+\frac{1}{(\lambda_1-\lambda_2)(\lambda_2-x)}$，二者显然共轭，只考虑第一部分，再把所有 $\lambda_1,\lambda_2$ 互换，二者相加。 设 $s=\lambda_1+\lambda_2,t=\lambda_1\lambda_2,f_n=\frac{\lambda_1^{n}-\lambda_2^{n}}{\lambda_1-\lambda_2}$。则 $f_0=0,f_1=1$。 有一个明显的线性递推 $f_n=s\cdot f_{n-1}-t\cdot f_{n-2}$，在 $n\leq 0$ 的情况下同样成立。 根据前面的结论，答案是： $$\frac{(1-\lambda_1)^{-a}\lambda_1^{-b-1}-(1-\lambda_2)^{-a}\lambda_2^{-b-1}}{\lambda_2-\lambda_1}+\sum_{i=0}^{a-1}\frac{(1-\lambda_1)^{i-a}-(1-\lambda_2)^{i-a}}{\lambda_1-\lambda_2}\binom{b+i}{i}$$ 到这里已经可以扩域计算了，不过还是简化一下： $$\frac{(1-\lambda_1)^{a}\lambda_1^{b+1}-(1-\lambda_2)^{a}\lambda_2^{b+1}}{(\lambda_1-\lambda_2)(1-s+t)^{a}t^{b+1}}-\sum_{i=0}^{a-1}g_{i-a}\binom{b+i}{i}$$ 其中后面 $g$ 是对于 $s'=2-s,t'=1-s+t$ 两个特征根的线性递推，也可以直接计算。 显然避不开 $f_{b}$ 的求解，二项式展开后，需要一个矩阵快速幂计算 $f_{b+1\sim b+a+1}$ 的值，复杂度 $O(a+\log b)$，可以认为是线性。 我们大胆推广猜测一下，任何低次多项式乘上 $\frac{1}{(1-x)^a}$ 都可以 $O(a)$ 通过对称式的办法计算。可是都这么暴力了，为什么不去写整式递推呢？