[問題案] 部分分数分解

[Maruoka842]

(任意) 問題ID: {ID} 問題名: {partial fraction decomposition}

参考資料: {https://t.co/e59zP7PiXm?amp=1}

問題概要

P(x) / \prod_{i=1}^k Q_i^{l_i}(x) を部分分数分解せよ。 ただし、 ・Q_i(x)は互いに素な多項式 ・\deg P(x) < \sum_{i=1}^k l_i \deg Q_i (x) だとする。より正確には P(x) / \prod_{i=1}^k Q_i^{l_i}(x) = \sum_{i=1}^k\sum_{j=1}^{l_i}C_{i,j}(x)/Q_i^{l_j}(x) と分解したときのC_{i,j}を求めよ。分解は一意に定まることが示せる。

入力

出力

制約

\sum_{i=1}^k l_i \deg Q_i (x) \leq 10^5

連立方程式をO(n³)で解くのは想定TLE

O(nlog²n) 想定 O(n²)を落とすのは諦める

あとでもう少し追記します。

[maspypy]

準備しようとしているものとは別問題になるかもしれないけど、f(x)/g(x)(1-x)^n の形の有理式の部分分数分解はたまに問われるイメージがあって、この形の場合の速い部分分数分解ライブラリも需要があるかもしれない。（解法も何も考えていないが）

https://github.com/yosupo06/library-checker-problems/issues/99 https://atcoder.jp/contests/s8pc-3/tasks/s8pc_3_g