有理真分式分解

关于公式编号，感性理解一下吧.... ## 有理真分式分解 考虑有理真分式 $\dfrac{P(x)}{Q(x)}$​​​​, 其中 $P(x),Q(x)\in \mathbb R[x]$​​ 且 $\deg P(x)<\deg Q(x)$. 我们知道, $Q(x)$​​ 可以唯一地分解为 $\mathbb R[x]$ 中若干个一次或二次不可约多项式的乘积 (这是代数基本定理和共轭复根结论的简单推论), 设 $$ Q(x)=c\times \Big(\prod\limits_{i=1}^n (x+a_i)^{p_i}\Big)\times \Big(\prod\limits_{j=1}^m(x^2+b_ix+c_i)^{q_i}\Big)\quad(c\ne 0), $$ 我们希望将真分式 $\dfrac{P(x)}{Q(x)}$​​ 分解为如下部分分式的和: $$ \dfrac{P(x)}{Q(x)}=\Big(\sum\limits_{i=1}^n \sum\limits_{j=1}^{p_i}\dfrac{A_{i,j}}{(x+a_i)^j}\Big)+\Big(\sum\limits_{i=1}^m\sum\limits_{j=1}^{q_i}\dfrac{B_{i,j}x+C_{i,j}}{(x^2+b_ix+c_i)^j}\Big), $$ 将其称为 $\dfrac{P(x)}{Q(x)}$ 的部分分式分解, 其中 $A_{i,j},B_{i,j},C_{i,j}\in \mathbb R$​​. --- ### Part 0 **定理 1. 对于任意 $P(x),Q(x)\in \mathbb R[x],\ \deg P(x)<\deg Q(x)$, 分解 (2) 都存在且唯一.** 我们希望通过解出 $A_{i,j},B_{i,j},C_{i,j}$​​ 来证明, 两边同时乘上 $Q(x)$​​ 得 $$ P(x)=\Big(\sum\limits_{i,j} A_{i,j}\times \dfrac{Q(x)}{(x+a_i)^j}\Big)+\Big(\sum\limits_{i,j}(B_{i,j}x+C_{i,j})\times \dfrac{Q(x)}{(x^2+b_ix+c_i)^j}\Big). $$ **引理 1. $Q(x)=(x+a)^n$​​​ 时, 分解 (2) 存在且唯一.** 证明: 根据 (3), 这等价于找到 $A_0,\ldots,A_{n-1}$ 使得 $$ P(x)=A_0+A_1(x+a)+A_2(x+a)^2+\ldots+A_{n-1}(x+a)^{n-1}, $$ 这是一个 $n$​​ 元线性方程组, 对照系数就可以写出 $n$​​​ 个方程, 我们发现系数矩阵的项 $M_{i,j}=[x^i](x+a)^j$, 所以这是一个上三角矩阵且对角线上全 $1$, 故 $\det M=1$​​, 方程组有唯一解. **引理 2. $Q(x)=(x^2+bx+c)^m$​​​ 时, 分解 (2) 存在且唯一.** 证明: 与引理 1 类似. **引理 3. 若 $A(x),B(x),C(x)\in \mathbb R[x]$​, 且 $A(x)$​ 与 $B(x)$​ 互素, $\deg C(x)<\deg A(x)+\deg B(x)$​, 则存在唯一的 $F(x),G(x)$​ 使得 $\deg F(x)<\deg B(x),\ \deg G(x)<\deg A(x)$​, 且 $C(x)=A(x)F(x)+B(x)G(x)$​​​ .** 证明: 先证存在性. 在多项式环 $\mathbb R[x]$ 中应用裴蜀定理, 由 $A(x),B(x)$ 互素知存在 $F_0(x),G_0(x)$ 使得 $A(x)F_0(x)+B(x)G_0(x)=1$, 故令 $F(x)=F_0(x)C(x)\bmod B(x),\ G(x)=G_0(x)C(x)\bmod A(x)$ 即可. 再证唯一性. 假设有两组不同的解 $A(x)F(x)+B(x)G(x)=A(x)F'(x)+B(x)G'(x)=C(x)$, 那么 $A(x)(F(x)-F'(x))=B(x)(G'(x)-G(x))$, 所以 $A(x)\mid G'(x)-G(x)$, 而 $\deg G'(x),\deg G(x)<\deg A(x)$, 所以只能有 $G'(x)-G(x)=0$ 即 $G'(x)=G(x)$, 同时 $F'(x)=F(x)$. 现在考虑证明定理 1. 设 $Q(x)$ 的因式分解如 (1), 令 $f(R(x))=\dfrac{Q(x)}{R(x)}\ \ (R(x)\mid Q(x))$​, 我们首先解出 $$ P(x)=\Big(\sum\limits_{i} A_i(x)f((x+a_i)^{p_i})\Big)+\Big(\sum\limits_{i}B_i(x)f((x^2+b_ix+c_i)^{q_i})\Big) $$ 中的 $A_i(x),B_i(x)$, 其中 $\deg A_i(x)<p_i,\ \deg B_i(x)<2q_i$. 由于 $x+a_i,\ x^2+b_ix+c_i$ 都是 $\mathbb R[x]$ 中的不可约多项式, 所以 $f((x+a_i)^{p_i}),\ f((x^2+b_ix+c_i)^{q_i})$ 两两互素, 因此对 $\deg G(x)$ 归纳应用引理 3 可以说明 $A_i(x),\ B_i(x)$ 存在且唯一. 式 (5) 其实等价于 $$ \dfrac{P(x)}{Q(x)}=\Big(\sum\limits_{i}\dfrac{A_i(x)}{(x+a_i)^{p_i}}\Big)+\Big(\sum\limits_{i}\dfrac{B_i(x)}{(x^2+b_ix+c_i)^{q_i}}\Big), $$ 再对每一项应用引理 1 或引理 2, 就证明了分解的存在性和唯一性, 定理 1 得证. --- 下面考虑如何求出真分式 $\dfrac{P(x)}{Q(x)}$​​ 的部分分式分解, 这里重新抄一次 (2) 式: $$ \dfrac{P(x)}{Q(x)}=\Big(\sum\limits_{i=1}^n \sum\limits_{j=1}^{p_i}\dfrac{A_{i,j}}{(x+a_i)^j}\Big)+\Big(\sum\limits_{i=1}^m\sum\limits_{j=1}^{q_i}\dfrac{B_{i,j}x+C_{i,j}}{(x^2+b_ix+c)^j}\Big), $$ 首先将 $Q(x)$​​​ 变为首一多项式, 即令 $Q(x),P(x)$​​ 同时乘上 $\dfrac{1}{c}$​​​. --- ### Part 1 考虑对于某个 $i\in [1,n]$ 如何求出全部的 $A_{i,j}\ (1\leq j\leq p_i)$, 我们首先将等式两边乘上 $(x+a_i)^{p_i}$, 就得到 $$ \dfrac{P(x)}{Q(x)/(x+a_i)^{p_i}}=\Big(\sum\limits_{j=1}^{p_i} A_{i,j}(x+a_i)^{p_i-j}\Big)+(x+a_i)^{p_i}\times \dfrac{R(x)}{Q(x)/(x+a_i)^{p_i}}, $$ 其中 $\dfrac{R(x)}{Q(x)/(x+a_i)^{p_i}}$ 就是将等式右边除了 $\dfrac{A_{i,j}}{(x+a_i)^j}$​ 以外的项通分的结果. 令 $Q_0(x)=\dfrac{Q(x)}{(x+a_i)^{p_i}}$, 在式 (8) 中带入 $x=-a_i$, 就有 $$ \dfrac{P(-a_i)}{Q_0(-a_i)}=A_{i,p_i}, $$ 这是因为右边的其他项都有因式 $(x+a_i)$​, 所以为零. 这样就求出了 $A_{i,p_i}$​. 接下来对 (8) 两边求 $k\ (k<p_i)$​​ 次导, 就得到 $$ \Big(\dfrac{P(x)}{Q_0(x)}\Big)^{(k)}=\Big(\sum\limits_{j=1}^{p_i-k}(p_i-j)^{\underline{k}}\times A_{i,j}\times (x+a_i)^{p_i-k-j}\Big)+\Big((x+a_i)^{p_i}\times \dfrac{R(x)}{Q_0(x)}\Big)^{(k)}, $$ 不难对 $k$​ 归纳证明右边第二个括号中的项 $\Big((x+a_i)^{p_i}\times \dfrac{R(x)}{Q_0(x)}\Big)^{(k)}$​​ 的分子有 $p_i-k$​ 重根 $a_i$​ (利用导数使得重根的重数减少 $1$​ 的性质). 因此带入 $x=-a_i$, 右边第二个括号中的项还是为 $0$​​, 也就有 $$ \Big(\dfrac{P}{Q_0}\Big)^{(k)}(-a_i)=k!\times A_{i,p_i-k}. $$ 因此对于每个 $k$​ 分别计算 $\Big(\dfrac{P}{Q_0}\Big)^{(k)}(-a_i)$​, 就得到了每个 $A_{i,j}$​​. --- ### Part 2 再考虑如何计算 $B_{i,j},C_{i,j}$, 下面是我自己编的做法, 其实和 $A_{i,j}$ 区别不大, 但计算量似乎非常大. 等式两边乘上 $(x^2+b_ix+c_i)^{q_i}$, 令 $Q_0(x)=\dfrac{Q(x)}{(x^2+b_ix+c_i)^{q_i}}$, 就得到 $$ \dfrac{P(x)}{Q_0(x)}=\Big(\sum\limits_{j=1}^{q_i}(B_{i,j}x+C_{i,j})(x^2+b_ix+c_i)^{q_i-j}\Big)+\Big((x^2+b_ix+c_i)^{q_i}\times\dfrac{R(x)}{Q_0(x)}\Big), $$ 同样两边求 $k\ (k<q_i)$​​ 次导, 得到 $$ \Big(\dfrac{P(x)}{Q_0(x)}\Big)^{(k)}=\Big(\sum\limits_{j=1}^{q_i} [(B_{i,j}x+C_{i,j})(x^2+b_ix+c_i)^{q_i-j}]^{(k)}\Big)+\Big((x^2+b_ix+c_i)^{q_i}\times\dfrac{R(x)}{Q_0(x)}\Big)^{(k)}. $$ 设 $x^2+b_ix+c_i$​​ 的两个复根为 $z,\bar z$​, 根据导数和重根的关系知右边第二个括号中的分子有 $q_i-k$​ 重根 $z,\bar z$​, 所以我们带入 $x=z$​, 右边第二个括号和第一个括号中的一部分就消失了, 具体地: $$ \Big(\dfrac{P}{Q_0}\Big)^{(k)}(z)=F^{(k)}(z) $$ 其中 $F(x)=\sum\limits_{j=q_i-k}^{q_i}(B_{i,j}x+C_{i,j})(x^2+b_ix+c_i)^{q_i-j}$. 对比左右两边的虚部和实部, 就可以得到有关 $B_{i,q_i-k},\ldots,B_{i,q_i},C_{i,q_i-k},\ldots,C_{i,q_i}$ 的 $2$ 个线性方程, 于是我们依次令 $k=0,\ldots,q_i-1$, 就可以每次用两个方程分别解出 $B_{i,q_i-k}$ 和 $C_{i,q_i-k}$ (实际上得到的是一个它们关于 $B_{i,q_i-k+1},\ldots,B_{i,q_i},C_{i.q_i-k+1},\ldots,C_{q_i}$ 的递推式). --- ### Part 3 上面介绍了一个通法, 当然还有一些别的办法计算部分分式分解, 有的通用, 有的不通用, 比如极限法, 留数定理法等, 我不太了解. 假分式也可以进行分式分解, 只不过先把 $P(x)$​ 除以 $Q(x)$ 的商拿出来, 然后再做剩下的真分式的分解. 下面介绍一些分式分解的很简单的应用. 在 oi 中, 式 (2) 可以用于一些线性递推的快速计算, 例如: > 例题: [ABC 241 Ex] Card Deck Score > > 有 $n$​​​ 个盒子, 第 $i$​​​ 个盒子里有 $b_i$​​​ 个球, 从各个盒子中取出总共 $m$​​​ 个球, 若第 $i$​​ 个盒子中取出了 $c_i$​​ 个球, 则这种取法的价值是 $\prod_{i=1}^n a_i^{c_i}$​​, 求所有取法的价值总和对 $P=998244353$​ 取模的结果, 同一盒子中的球不可区分. > > $1\leq n\leq 16,\ 1\leq m\leq 10^{18},\ 1\leq a_i\leq 998244352,\ 1\leq b_i\leq 10^{17}$, 保证 $a_i$ 两两不同. 考虑经典的容斥, 先不考虑第 $i$ 个盒子最多取 $b_i$ 个的限制, 再钦定某个子集中所有盒子都违反了 $b_i$​ 的限制进行容斥, 则对于每个子集, 问题转化为: 从 $n$ 个盒子中一共取出 $m-S$ 个球, 不考虑 $b_i$ 的限制, 问价值之和. 显然答案为 $$ [x^{m-S}]\prod\limits_{i=1}^n\dfrac{1}{1-a_ix}. $$ 式 (15) 中的分式代表了一个线性递推, 可以使用各种方法做到 $O(n^3\log m),\ O(n^2\log m),\ O(n\log n\log m)$ 等复杂度. 进一步优化, 对式 (15) 中的分式进行分式分解, 那么答案就是 $$ \sum\limits_{i=1}^n[x^{m-S}]\dfrac{A_i}{1-a_ix}=\sum\limits_{i=1}^nA_i\times a_i^{m-S} $$ 这样, 复杂度就是 $O(n\log P)$​ (利用欧拉定理). 而预处理 $A_i$ 的复杂度为 $O(\operatorname{poly}(n,\log P))$, 所以本题总复杂度为 $O(2^n\times n\log P)$. 在数学中, 式 (2) 可以用于求有理分式的不定积分. 对于整式以及分母是 $(x+a)^k$, 分子零次的真分式, 我们有: $$ \int(a_nx^n+\ldots+a_0) \text{d}x=\dfrac{a_n}{n+1}x^{n+1}+\ldots+a_0x+C; $$ $$ \int\dfrac{A}{(x+a)^k} \text{d}x=\begin{cases}\dfrac{A}{(1-k)(x+a)^{k-1}}+C & (k\ne 1) \\ A\ln|x+a|+C & (k=1)\end{cases}. $$ 而对于分母是 $(x^2+bx+c)^k$ 且 $x^2+bx+c$​ 不可约, 分子一次的真分式, 有 (抄书): $$ \int\dfrac{Bx+C}{(x^2+b_ix+c_i)^k}\text{d}x=\int \dfrac{\alpha u+\beta}{(u^2+a^2)^k}\text{d}u\quad (u=x+\dfrac{p}{2},\ a=\sqrt{c-\dfrac{b^2}{4}},\ \alpha=B,\ \beta=C-\dfrac{Bb}{2}), $$ 将 $\alpha u$ 和 $\beta$ 分开来算, 不管常数 $\alpha,\beta$, 对于前者有 $$ \int \dfrac{u}{(u^2+a^2)^k}\text{d}u=\int\dfrac{\text{d}(u^2+a^2)}{2(u^2+a^2)^k}=\begin{cases}\dfrac{1}{2\times (1-k)(u^2+a^2)^{k-1}}+C & (k\ne 1) \\ \dfrac{1}{2}\ln (u^2+a^2)+C & (k=1)\end{cases} $$ 对于后者, 使用分部积分获得递推式 (抄书): $$ I_k=\int \dfrac{1}{(u^2+a^2)^k}\text{d}u $$ $$ I_{k}=\int \dfrac{\text{d}u}{\text{d}u}\times \dfrac{1}{(u^2+a^2)^k}\text{d}u=\dfrac{u}{(u^2+a^2)^k}-\int u\times \dfrac{\text{d}}{(u^2+a^2)^k\text{d}u}\text{d}u $$ $$ =\dfrac{u}{(u^2+a^2)^k}+2k\int \dfrac{u^2}{(u^2+a^2)^{k+1}}\text{d}u $$ $$ =\dfrac{u}{(u^2+a^2)^k}+2k\int \dfrac{(u^2+a^2)-a^2}{(u^2+a^2)^{k+1}}\text{d}u $$ $$ =\dfrac{u}{(u^2+a^2)^k}+2kI_k-2ka^2I_{k+1}. $$ 稍作整理, 得到: $$ I_{k+1}=\dfrac{u}{(u^2+a^2)^k\times 2ka^2}+\dfrac{2k-1}{2ka^2}I_k $$ $$ I_1=\int \dfrac{1}{u^2+a^2}\text{d}u=\dfrac{1}{a}\arctan(\dfrac{u}{a})+C. $$