https://atcoder.jp/contests/abc245/tasks/abc245_d
多项式除法
输入一个N次多项式A
输入一个N+M次多项式C
找到一个次数是M的多项式B
使得多项式A乘以多项式B等于多项式C
不需要取模，可能有负数，保证有解
\section{多项式}
给定一个环 （通常是交换环，可以是有理数、实数或者复数等等）以及一个未知数 ，则任何形同：
的代数表达式叫做 上的一元多项式。其中 是中的元素。未知数不代表任何值，
但环 上的所有运算都对它适用。
对于一元多项式来说，未知数在多项式各项中最大的次数称为多项式的次数。
注意$n$次的多项式最多可以有$n+1$项。
\begin{enumerate}
\item 多项式乘法
\item 多项式乘法逆
\item 多项式除法
\item 多项式快速幂
\item 多项式复合函数
\item 多项式复合逆
\item 多项式多点求值
\item 多项式三角函数
\end{enumerate}
\subsection{多项式加法减法}
两个多项式相加可以看作是对两组单项式的和进行重组与合并同类项。
通过加法结合律，可以将同类项放在一起，合并之后就得到了两个多项式的和。
\subsection{多项式乘法}
计算两个多项式相乘时，首先使用乘法对加法的分配律将各项拆出，然后运用乘法结合律整合每一项，
最后和加法一样整合同类项，就能得到乘积多项式。
\subsection{多项式求导}
按照定义做即可$$(x^n)' = n x^{n - 1}$$。
\subsection{多项式积分}
按照定义做即可$$ \int x^n \mathrm{d}x = \frac{n + 1} x^{n + 1}$$。
一般认为积分后不加常数项（常数项为$0$）
\subsection{多项式除法取模}
和整数之间的带余除法类似，一元多项式之间也可以进行带余除法。
可以证明，设有多项式 $A(x)$ 和非零多项式 $B(x)$ ，则存在唯一的多项式 $Q(x)$ 和 $R(x)$，满足：
$$A(x) = Q(x)B(x) + R(x)$$
也可以简单地认为
$$A(x) \bmod B(x) = R(x)$$
\subsection{多项式乘法逆}
显然对于次数大于$1$的多项式$A(x)$，不可能找到多项式$B(x)$使得
$$A(x) B(x) = 1$$
和数论的情况类似，如果
$$A(x) B(x) = 1 \pmod{x^n}$$
那么称 $B(x)$ 为 $A(x)$ 在 $\bmod{x^n}$ 意义下的逆元。
\subsection{多项式开根}
和数论的情况类似，如果
$$B^2(x) = A(x) \pmod{x^n}$$
那么称 $B(x)$ 为 $A(x)$ 在 $\bmod{x^n}$ 意义下的平方根。
\subsection{信息学竞赛相关}
为了计算精确，题目一般对质数取模。
为了可以使用FFT或NTT，$n$一般是$2$的次幂，质数减一之后是$n$的倍数。
即存在$n$次单位根。
如果$n$不是$2$的次幂，可以算出一个比$n$大的$2$的次幂结果，只取前$n$项。
如果取模的数字性质不好，需要比较麻烦的三模数NTT，或者拆系数FFT。
\subsection{多项式求逆}
假设$n$是$2$的次幂，可以递归解决这个问题。
如果$n$不是$2$的次幂，可以算出一个比$n$大的$2$的次幂结果，只取前$n$项。
如果$n = 1$，那么$A(x)$只有常数项，如果非零，直接乘法逆元，如果为零，那么无解。
如果$n > 1$，先求出$n/2$的答案，即
$$A(x) B_0(x) = 1 \pmod{x^{n/2}}$$
注意到对于要求的$B(x)$满足
$$A(x) B(x) = 1 \pmod{x^{n}}$$
也满足
$$A(x) B(x) = 1 \pmod{x^{n/2}}$$
相减可以得到
$$A(x) (B(x) - B_0(x)) = 0 \pmod{x^{n/2}}$$
因为$A(x)$可逆，所以可以消去
$$(B(x) - B_0(x)) = 0 \pmod{x^{n/2}}$$
两侧平方，取模的数字同样平方
$$B(x)^2 - 2 B(x) B_0(x) + B_0^2(x) = 0 \pmod{x^{n}}$$
两遍同时乘以$A(x)$，注意到$B(x)$是$A(x)$的逆元，他们乘积为$1$。
$$B(x) - 2 B_0(x) + A(x) B_0^2(x) = 0 \pmod{x^{n}}$$
移项之后得到
$$B(x) = 2 B_0(x) - A(x) B_0^2(x) \pmod{x^{n}}$$
总复杂度为$T(n) = T(n / 2) + O(\text{多项式乘法})$。
如果使用$O(n \log n)$的多项式乘法，那么复杂度为$O(n \log n)$。
如果使用$O(n^2)$的多项式乘法，那么复杂度为$O(n^2)$。
\subsection{多项式开根}
假设$n$是$2$的次幂，可以递归解决这个问题。
如果$n$不是$2$的次幂，可以算出一个比$n$大的$2$的次幂结果，只取前$n$项。
如果$n = 1$，那么$A(x)$只有常数项，如果二次剩余，直接二次剩余，如果二次非剩余，直接二次非剩余。
如果$n > 1$，先求出$n/2$的答案，即
$$B_0^2(x) = A(x) \pmod{x^{n/2}}$$
注意到对于要求的$B(x)$满足
$$B^2(x) = A(x) \pmod{x^{n}}$$
也满足
$$B^2(x) = A(x) \pmod{x^{n/2}}$$
相减可以得到
$$(B(x) + B_0(x))(B(x) - B_0(x)) = 0 \pmod{x^{n/2}}$$
像整数开根一样，会有两个解，不妨认为后者为零
$$(B(x) - B_0(x)) = 0 \pmod{x^{n/2}}$$
两侧平方，取模的数字同样平方
$$B(x)^2 - 2 B(x) B_0(x) + B_0^2(x) = 0 \pmod{x^{n}}$$
将$B(x)^2$替换为$A(x)$
$$A(x) - 2 B(x)B_0(x) + B_0^2(x) = 0 \pmod{x^{n}}$$
移项之后得到
$$B(x) = \frac{A(x) + B_0^2(x)}{2 B_0(x)} \pmod{x^{n}}$$
除法部分直接乘以分母的逆元。
总复杂度为$T(n) = T(n / 2) + O(\text{多项式乘法}) + O(\text{多项式求逆})$。
如果使用$O(n \log n)$的多项式乘法，那么复杂度为$O(n \log n)$。
如果使用$O(n^2)$的多项式乘法，那么复杂度为$O(n^2)$。
\subsection{多项式除法取模}
对于一个$n$次多项式$A(x)$，设
$A^R(x) = x^n A(1/x)$
即把$x$换为$\frac{1}{x}$，再乘以$x^n$；这一步相当于把多项式的系数前后 \texttt{reverse}。
设$A(x)$是$n$次多项式，$B(x)$是$m$次多项式，那么$Q(x)$是$n-m$次多项式，$R(x)$的次数小于$m$。
$$A(x) = Q(x)B(x) + R(x)$$
把$x$换为$\frac{1}{x}$，再乘以$x^n$。
$$x^n A(\frac{1}{x}) = x^{n-m} Q(\frac{1}{x}) x^m B(\frac{1}{x}) + x^{n-m+1} x^{m-1}R(\frac{1}{x})$$
替换成$A^R$，可以得到
$$A^R(x) = Q^R(x) B^R(x) + x^{n-m+1}R^R(x)$$
两边同时对$x^{n-m+1}$取模，可以得到
$$A^R(x) = Q^R(x) B^R(x) \pmod{x^{n-m+1}}$$
而$Q^R$恰好是一个$n-m$次的多项式，注意到$B^R(x)$非零，可以求逆元。
$$Q^R(x) = \frac{A^R(x)}{B^R(x)} \pmod{x^{n-m+1}}$$
求出$Q(x)$后，可以直接计算得到$R(x) = A(x) - Q(x)B(x)$。
总复杂度为$O(\text{多项式乘法}) + O(\text{多项式求逆})$。
如果使用$O(n \log n)$的多项式乘法，那么复杂度为$O(n \log n)$。
\subsection{多项式Log}
$$\log(1 + x) = \sum_{n = 1}^{+\infty} \frac{(-1)^{n + 1}}{n}x^n$$
对于多项式$A(x)$来说
$$\log(A(x)) = \log(1 + (A(X) - 1)) = \sum_{n = 1}^{+\infty} \frac{(-1)^{n + 1}}{n}(A(x) - 1)^n$$
特别注意，如果$A(x) - 1$常数项非$0$，是不能取对数的。
$$(\log(A(x)))' = \frac{A'(x)}{A(x)}$$
$$\log(A(x)) = \int \frac{A'(x)}{A(x)} \mathrm{d}x$$
用定义暴力算的复杂度为$O(n^2)$。
总复杂度为$O(\text{多项式乘法}) + O(\text{多项式求逆})$。
如果使用$O(n \log n)$的多项式乘法，那么复杂度为$O(n \log n)$。
\subsection{多项式Exp}
$$\exp(x) = \sum_{n = 1}^{+\infty} \frac{x^n}{n!}$$
对于多项式$A(x)$来说
$$\exp(A(x)) = \sum_{n = 1}^{+\infty} \frac{A^n(x)}{n!}$$
特别注意，如果$A(x)$常数项非$0$，是不能取指数的。
对于一个已知的函数$G(F(x))$，求多项式$F(x)$使得$G(F(x)) = 0$。
注意$G(F(x))$是以多项式$F(x)$为参数的函数，而不是函数的嵌套。
用类似于倍增的牛顿迭代，首先求出$F(x)$，使得
$$G(F(x)) = 0 \pmod{x}$$
如果已知$G(F_0(x)) = 0 \pmod{x^n}$，可以将$G$在$F_0(x)$的位置展开。
$$G(F(x)) = G(F_0(x)) + G'(F_0(x)) \times (F(x) - F_0(x)) +
\frac{G''(F_0(x)) \times (F(x) - F_0(x))^2}{2!} + \cdots$$
其中$G(F(x)) = 0 \pmod{x^{2n}}$，显然$(F(x) - F_0(x)) = 0 \pmod{x^n}$。（显然吗？）
那么$(F(x) - F_0(x))^2 = 0 \pmod{x^{2n}}$，所以二次项及之后的部分都不需要考虑。
$$G(F_0(x)) + G'(F_0(x)) \times (F(x) - F_0(x)) = 0 \pmod{x^{2n}}$$
解得
$$F(x) = F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} \pmod{x^{2n}}$$
在本题中$G(F(x)) = \log(F(x)) - A(x), G'(F(x)) = \frac{1}{F(x)}$，所以
$$F(x) = F_0(x) - F_0(x) (\log(F_0(x)) - A(x))\pmod{x^{2n}}$$
$$F(x) = F_0(x) (1 - \log(F_0(x)) + A(x))\pmod{x^{2n}}$$
$F_0(x)$只要次数较低的$n$项正确即可，前面是否正确无所谓。
用定义暴力算的复杂度为$O(n^2)$。
总复杂度为$T(n) = T(n / 2) + O(\text{多项式乘法}) + O(\text{多项式求逆})$。
如果使用$O(n \log n)$的多项式乘法，那么复杂度为$O(n \log n)$。
\subsection{多项式开$k$次方}
如果多项式的常数项为$1$，那么可以通过取Log，除以$k$，再Exp的方法来做。
如果常数项不为$1$，那么需要提出常数项，单独对常数项做一次开$k$次方。
\subsection{泰勒展开}
\href{https://en.wikipedia.org/wiki/Taylor_series}{泰勒展开}
建议记住常见的泰勒展开。
\subsection{拉格朗日插值}
\href{https://en.wikipedia.org/wiki/Lagrange_polynomial}{拉格朗日插值法}
\href{https://oi-wiki.org/math/lagrange-poly/}{OI Wiki}
关键点都差不多，主要有两类问题。已知$n$个点$(x_i, y_i)$，确定一个$n-1$次多项式。
\begin{itemize}
\item 求出这个多项式在一个新的点的值。
\item 求出多项式每一项的系数。
\end{itemize}
拉格朗日插值在特殊情况下，可以推广到多个变量的情况，但是几乎没有用。
不妨考虑多种颜色的边的生成树计数。
\subsection{多项式多点求值}
输入一个$n-1$次多项式$A(x)$的系数，和一个$x_0$，求$A(x_0)$，可以用秦九韶算法。
如果对多个点$x_0, x_1, \ldots, x_{n-1}$同时求值呢？暴力是$O(n^2)$的。
把要求值的点任意分成两部分，比如
$$X_0 = \{x_0, x_1, \ldots, x_{n/2 - 1}\},
X_1 = \{x_{n/2}, x_{n/2+1}, \ldots, x_{n - 1}\}$$
定义多项式
$$P_0(x) = \prod_{x_i \in X_0} (x - x_i),
P_1(x) = \prod_{x_i \in X_1} (x - x_i)$$
计算$P_0(x)$和$P_1(x)$可以递归和分治FFT来计算。
对于$X_i$里的数，只需要带入$A(x) \bmod P_i(x)$即可。
多项式取模时间复杂度$O(n \log n)$。
即$T(n) = 2T(n / 2) + O(n \log n) = O(n \log^2 n)$。
\subsection{多项式快速插值一}
\href{https://blog.csdn.net/qq_35649707/article/details/83625203}{快速插值$O(n \log^2 n)$}
\subsection{多项式快速插值二}
\href{https://blog.csdn.net/qq_35649707/article/details/83625203}{快速插值$O(n \log^3 n)$}
输入$n$个点$(x_i, y_i)$，希望求一个$n-1$次多项式，通过所有点。
把$n$个点任意分成两部分，比如
$X_0 = \{x_0, x_1, \ldots, x_{n/2 - 1}\}$ 和
$X_1 = \{x_{n/2}, x_{n/2+1}, \ldots, x_{n - 1}\}$。
对于$X_0$求出对应的多项式$A_0(x)$。
定义多项式
$P_0(x) = \prod_{x_i \in X_0} (x - x_i)$。
最终答案一定是
$$A(x) = B_1(x) P_0(x) + A_0(x)$$
关键在于$B_1(x)$是什么。
也就是说，对于$x_i \in X_1$，有$y_i = B_1(x_i) P_0(x_i) + A_0(x_i)$。
可以用快速求值，求出$P_0(x_i)$和$A_0(x_i)$。
可得$B_1(x_i) = \frac{y_i - A_0(x_i)}{P_0(x_i)}$。
递归求解$B_1(x)$即可。
多点求值的复杂度为$O(n \log^2 n)$。
即$T(n) = 2T(n / 2) + O(n \log^2 n) = O(n \log^3 n)$。
\includeproblem{other}{fhqcircle}
\includeproblem{uyhip}{2013jun}
\includeproblem{luogu}{P2312}
\includeproblem{bzoj}{2742}
\includeproblem{codeforces}{622F}
\includeproblem{hdu}{4651} % partition
\includeproblem{hdu}{4658} % partition k
\includeproblem{hdu}{3205} % 分圆多项式
\includeproblem{hdu}{6414} % baidu astar
\includeproblem{codechef}{BIKE}
\includeproblem{codeforces}{917D}
\includeproblem{codeforces}{102028J}