多项式各种操作

PS：洛谷上有大部分以下操作的模板题。

感谢 cyk 巨神 的 多项式算法合集。

多项式求逆

problem:

给定一个 $(n-1)$ 次多项式 $A(x)$ ，求多项式 $B(x)$ 满足：

$$A(x)B(x)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

solution:

为了方便，我们设 $n=2^k(k>0)$（若 $n$ 不是 $2$ 的整数次幂，可以像 $fft$ 那样强行扩大到 $2^k$）。

用类似于倍增的方法，即假设我们已知

$$A(x)C(x)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\frac{n}{2}})$$

因为 $A(x)B(x)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$，那么有 $A(x)B(x)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\frac{n}{2}})$，两式相减得：

$$A(x)(B(x)-C(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\frac{n}{2}})$$

那么消掉 $A(x)$，两边平方得：

$$B^2(x)+C^2(x)-2B(x)C(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

这个时候再把 $A(x)$ 乘回去，得到：

$$A(x)(B^2(x)+C^2(x)-2B(x)C(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

然后再综合 $A(x)B(x)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$ 化简，最终得到：

$$B(x)=2C(x)-A(x)C^2(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

时间复杂度 $O(n\log n)$。

code:

注意代码中用的变量和推导中用的不一样。

typedef vector<int> poly;
poly Inv(poly A,int len){
poly C,B(1,Power(A[0],P-2));
for(int limit=4;limit<(len<<2);limit<<=1){
init(limit);
C=A,C.resize(limit>>1);
C.resize(limit),NTT(C,limit,1);
B.resize(limit),NTT(B,limit,1);
for(int i=0;i<limit;++i)
B[i]=mul(B[i],dec(2,mul(B[i],C[i])));
NTT(B,limit,-1),B.resize(limit>>1);
}
B.resize(len);return B;
}

多项式开根

problem:

已知一个 $(n-1)$ 次多项式 $A(x)$，求多项式 $B(x)$ 满足

$$B^2(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

保证 $A(0)=1$。

solution:

和求逆一样，为了方便，记 $n=2^k(k>0)$。

假设我们知道

$$C^2(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\frac{n}{2}})$$

因为 $B^2(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$，那么有 $B^2(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\frac{n}{2}})$，那么

$$B(x)-C(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\frac{n}{2}})$$

平方，得：

$$B^2(x)+C^2(x)-2B(x)C(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

又由于 $B^2(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$，所以：

$$B(x)=\frac{A(x)}{2C(x)}+\frac{C(x)}{2}(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

不难发现需要用到上面所说的多项式求逆。

时间复杂度 $O(n\log n)$，好像常数有点大。

code:

typedef vector<int> poly;
poly Sqrt(poly A,int len){
poly B(1,1),C,D;
for(int limit=4;limit<(len<<2);limit<<=1){
C=A,C.resize(limit>>1);
init(limit),D=Inv(B,limit>>1);
C.resize(limit),NTT(C,limit,1);
D.resize(limit),NTT(D,limit,1);
for(int i=0;i<limit;++i)
C[i]=mul(C[i],D[i]);
NTT(C,limit,-1),B.resize(limit>>1);
for(int i=0;i<(limit>>1);++i)
B[i]=mul(inv2,add(B[i],C[i]));
}
B.resize(len);return B;
}

多项式除法 $\&$ 取模

problem:

给定一个 $n$ 次多项式 $A(x)$ 和一个 $m$ 次多项式 $B(x)$，求一个 $(n-m)$ 次多项式 $C(x)$ 和 $(m-1)$ 次多项式 $D(x)$ 满足：

$$A(x)=B(x)C(x)+D(x)$$

solution:

对于一个最高项次数为 $n$ 的多项式 $A(x)$，我们考虑对它进行一个操作，即令 $A^R(x)=x^{n}A(\frac{1}{x})$。

发现 $A^R(x)$ 就是将 $A(x)$ 的系数反转的式子（可以代几个 $n$ 比较小的多项式来帮助自己理解）。

现在的式子是：

$$A(x)=B(x)C(x)+D(x)$$

其中，$A(x)$ 最高项为 $n$，$B(x)$ 最高项为 $m$，$C(x)$ 最高项为 $n-m$，$D(x)$ 的最高项为 $m-1$。

那么两边同时乘 $x^n$，并将 $\frac{1}{x}$ 代入，得到：

$$x^{n}A(\frac{1}{x})=x^{m}B(\frac{1}{x})x^{n-m}C(\frac{1}{x})+x^{n-m+1}\times x^{m-1}D(\frac{1}{x})$$

通过上面的公式，即 $A^R(x)=x^{n}A(\frac{1}{x})$，得到：

$$A^R(x)=B^R(x)C^R(x)+x^{n-m+1}{D}^R(x)$$

考虑在 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^{n-m+1}$ 意义下，$A,B$ 已知，$C$ 最高为 $n-m$ 不影响，而 $D$ 被消去。

所以我们有：

$$A^R(x)\equiv B^R(x)C^R(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{n-m+1})$$

用多项式求逆即可解出 $C^R(x)$，也就解出了 $C(x)$。

最后把 $C(x)$ 代回去就可以解出 $D(x)$。

复杂度 $O(n\log n)$。

code:

PS：代码中多项式的 $\ast$ 和 $-$ 是重载过的。

typedef vector<int> poly;
poly operator/(poly A,poly B){
int limit=1,len=A.size()-B.size()+1;
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
while(limit<=len)
limit<<=1;
B=Inv(B,limit),B.resize(len);
A=A*B,A.resize(len);
reverse(A.begin(),A.end());
return A;
}
poly operator%(poly A,poly B){
poly C=A-(A/B)*B;
C.resize(B.size()-1);
return C;
}

多项式微积分（求导 $\&$ 积分）

solution:

令 $f(x)=x^n$，那么它的导数 $f^{\prime }(x)=n{x}^{n-1}$，根据这个可以快速求多项式的导数。

证明如下：
首先根据导数定义，有：

$$f^{\prime }(x)=\underset{\Delta x\to 0}{\lim }\frac{(x+\Delta x{)}^n-x^n}{\Delta x}$$

用二项式定理展开，得到：

$$\begin{array}{rl}{f}^{\prime }(x)& =\underset{\Delta x\to 0}{\lim }\frac{{\sum }_{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i\Delta x^{n-i}-x^n}{\Delta x}\\ & =\underset{\Delta x\to 0}{\lim }\frac{{\sum }_{i=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i\Delta x^{n-i}+x^n\Delta x^0-x^n}{\Delta x}\\ & =\underset{\Delta x\to 0}{\lim }\sum _{i=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i\Delta x^{n-i-1}\\ & =\underset{\Delta x\to 0}{\lim }\sum _{i=0}^{n-2}\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i\Delta x^{n-i-1}+\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)x^{n-1}\end{array}$$

又由于有限个无穷小的乘积依旧是无穷小，所以得到：

$$f^{\prime }(x)=\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)x^{n-1}=n{x}^{n-1}$$

证毕。

积分好像可以简单理解为导数的逆运算，还不是很会。。。

code:

PS：inv 数组是预处理的逆元。

typedef vector<int> poly;
poly Deriv(poly A){
for(int i=0;i<A.size()-1;++i)
A[i]=mul(A[i+1],i+1);
A.pop_back();return A;
}
poly Integ(poly A){
A.push_back(0);
for(int i=A.size()-1;i;--i)
A[i]=mul(A[i-1],inv[i]);
A[0]=0;return A;
}

多项式 Ln

problem:

给出 $(n-1)$ 次多项式 $A(x)$，求一个 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$ 下的多项式 $B(x)$，满足：

$$B(x)\equiv \ln A(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

保证 $A(0)=1$。

solution:

有一个结论，即若 $B(x)=\ln A(x)$，则 $A^{\prime }(x)=A(x)B^{\prime }(x)$。

证明如下：
首先有链式法则，即对于复合函数 $(g\circ f)(x)=g(f(x))$，有 $(g\circ f{)}^{\prime }(x)=g^{\prime }(f(x))f^{\prime }(x)$。
那么对于 $B(x)=\ln A(x)$，两边同时求导，得到 $B^{\prime }(x)=(\ln A(x){)}^{\prime }$。
等式右边可以看做一个复合函数，用链式法则化简后就是 $({\ln }^{\prime }A(x))A^{\prime }(x)=\frac{A^{\prime }(x)}{A(x)}$。
带回去，即可得到 $A^{\prime }(x)=A(x)B^{\prime }(x)$。
证毕。

那么 $B^{\prime }(x)=\frac{A^{\prime }(x)}{A(x)}$，给 $A(x)$ 求逆、求导就可以算出 $B^{\prime }(x)$。

然后再对 $B^{\prime }(x)$ 积分就能解出 $B(x)$。

code:

typedef vector<int> poly;
poly Ln(poly A,int len){
A=Integ(Deriv(A)*Inv(A,len)),A.resize(len);
return A;
}

多项式 Exp

前置知识 $1$：泰勒展开

泰勒展开是将一个在 $x=x_0$ 处具有 $n$ 阶导数的函数 $f(x)$ 利用关于 $(x-x_0)$ 的 $n$ 次多项式来逼近函数的方法。

若函数 $f(x)$ 在包含 $x_0$ 的某个闭区间 $[a,b]$ 上具有 $n$ 阶导数，且在开区间 $(a,b)$ 上具有 $(n+1)$ 阶导数，则对闭区间 $[a,b]$ 上任意一点 $x$，下式成立：

$$f(x)=\frac{f(x_0)}{0!}+\frac{f^{\prime }(x_0)}{1!}(x-x_0)+\frac{f^{\prime \prime }(x_0)}{2!}(x-x_0{)}^2+\cdots +\frac{f^{(n)}(x_0)}{n!}(x-x_0{)}^n+\cdots$$

我简单说一下我理解的泰勒展开。

等式右边的式子是一个多项式，所以我们的目标就是找一个多项式 $g(x)$，使它与 $f(x)$ 完全相同。

首先我们保证初始点 $g(x_0)=f(x_0)$。

在此基础上，考虑曲线的变化趋势，即导数，保证在此处的导数相同，即 $g^{\prime }(x_0)=f^{\prime }(x_0)$。

要进一步精确化，再考虑凹凸性，由于表征图像的凹凸性的参数为导数的导数，我们让二者导数的导数相等，即 $g^{\prime \prime }(x_0)=f^{\prime \prime }(x_0)$。

那么以此类推，继续精确，让 $x_0$ 更高阶的导数相等，即 $g^{(n)}(x_0)=f^{(n)}(x_0)$。

上面的式子归纳一下，就是 $\forall i,g^{(i)}(x_0)=f^{(i)}(x_0)$。

因为 $x^n$ 的导数为 $n{x}^{n-1}$，所以求 $g(x)$ 第 $i$ 阶导数时为 $a_i\times i!=f^{(i)}(x_0)$，所以 $a_i=\frac{f^{(i)}(x_0)}{i!}$。

可以看看这个，对理解泰勒展开会有帮助。

前置知识 $2$：牛顿迭代

摘自 Miskcoo’s Space 的牛顿迭代法在多项式运算的应用。

有这样一个问题，即已知一个函数 $g(x)$，求一个多项式 $f(x)\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$，满足方程

$$g(f(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

首先在 $n=1$ 的时候，$g(f(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}x)$，这是可以直接求出来的。

现在假设已经求出了 $g(f_0(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\lceil \frac{n}{2}\rceil })$，考虑如何扩展到 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$ 下。

我们把 $g(f(x))$ 在 $f_0(x)$ 进行泰勒展开，得到：

$$g(f(x))=g(f_0(x))+\frac{g^{\prime }(f_0(x))}{1!}(f(x)-f_0(x))+\frac{g^{\prime \prime }(f_0(x))}{2!}(f(x)-f_0(x){)}^2+\cdots$$

首先显然有 $f(x)\equiv f_0(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\lceil \frac{n}{2}\rceil })$，所以 $f(x)-f_0(x)$ 最低项次数一定大于 $\lceil \frac{n}{2}\rceil$。因此在 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$ 意义下，整个式子从 $(f(x)-f_0(x){)}^2$ 这一项开始都为 $0$ 了，也即：

$$g(f(x))\equiv g(f_0(x))+g^{\prime }(f_0(x))(f(x)-f_0(x))(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

又因为 $g(f(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$，得到

$$f(x)\equiv f_0(x)-\frac{g(f_0(x))}{g^{\prime }(f_0(x))}(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

这样就大功告成了。

OK，下面就步入正题，多项式 Exp。

problem:

给出 $(n-1)$ 次多项式 $A(x)$，求一个 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$ 下的多项式 $B(x)$，满足：

$$B(x)\equiv e^{A(x)}(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

保证 $A(0)=0$。

solution:

发现原问题可以转化一下，即求解：

$$\ln B(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

还是令 $n=2^k$，假设我们已经知道了 $\ln B_0(x)-A(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\frac{n}{2}})$。

构造 $P(B(x))=\ln B(x)-A(x)$，那么 $P^{\prime }(B(x))=\frac{1}{B(x)}$

那么按照牛顿迭代的推理可得：

$$B(x)\equiv B_0(x)-\frac{P(B_0(x))}{P^{\prime }(B_0(x))}\equiv B_0(x)(1-\ln B_0(x)+A(x))(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

时间复杂度 $O(n\log n)$。

code:

typedef vector<int> poly;
poly Exp(poly A,int len){
poly B(1,1),C;A.resize(len<<1);
for(int limit=2;limit<(len<<1);limit<<=1){
C=Ln(B,limit);
for(int i=0;i<limit;++i)
C[i]=dec(A[i],C[i]);
C[0]=add(C[0],1),B=B*C;
B.resize(limit);
}
B.resize(len);return B;
}

多项式快速幂

problem:

给定一个 $(n-1)$ 次多项式 $A(x)$，求一个在 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$ 意义下的多项式 $B(x)$，满足：

$$B(x)\equiv A^k(x)(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$$

保证 $A(0)=1$。

solution:

如果直接用快速幂+$ntt$的话，时间复杂度是 $O(n{\log }^{2}n)$ 的，而且常数还比较大。

所以我们换一种方法，即发现：

$$A^k(x)=(e^{\ln A(x)}{)}^k=e^{k\times \ln A(x)}$$

所以我们用多项式 Ln,Exp 就可以了。

时间复杂度 $O(n\log n)$。

code:

typedef vector<int> poly;
poly Power(poly A,int len,int k){
A=Exp(Ln(A,len)*k,len),A.resize(len);
return A;
}

多项式多点求值

problem:

给定一个 $n$ 次多项式 $f(x)$，并给出 $m$ 个整数 $a_i$，请你对于 $\forall i\in [1,m]$，求出 $f(a_i)$。

solution:

首先，根据余式定理，我们有：

$$f(x)\equiv f(x_0)(\mathrm{m}\mathrm{o}\mathrm{d}(x-x_0))$$

简单写一下它的证明：
令 $f(x)=g(x)(x-x_0)+A(x)$，那么 $A(x)$ 为就是 $f(x)$ 对 $(x-x_0)$ 取模的结果，即 $f(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}(x-x_0))$。
由于 $(x-x_0)$ 的最高项次数为 $1$，所以 $A(x)$ 最高项次数为 $0$，即为常数项。
把 $x_0$ 代入 $f(x)$，得到 $f(x_0)=g(x_0)(x_0-x_0)+A(x_0)=A(x)$，所以就有 $f(x)\equiv f(x_0)(\mathrm{m}\mathrm{o}\mathrm{d}(x-x_0))$。

但是直接这样做是不行的，对于一个点，多项式取模是 $O(n\log n)$ 的，甚至比 $O(n)$ 的暴力还慢。

然后考虑用分治优化。

令 $G_{l,r}(x)=\prod _{i=l}^r(x-x_i)$，我们现在已经算出了 $f(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}\prod _{i=l}^r(x-x_i))$，因此只需要用 $A(x)$ 分别对 $G_{l,\lfloor \frac{l+r}{2}\rfloor }(x)$ 和 $G_{\lfloor \frac{l+r}{2}\rfloor +1,r}(x)$ 取模，再递归下去。分治到叶子的时候，就只剩下 $f(x)\equiv A(x)(\mathrm{m}\mathrm{o}\mathrm{d}(x-x_i))$，此时的 $A(x)$ 就是 $i$ 的答案。

每个 $G(x)$ 可以提前分治$ntt$预处理出来。

时间复杂度 $T(n)=T(\frac{n}{2})+O(n\log n)=O(n{\log }^{2}n)$。

不知道为什么跑得贼慢，也许是我自带大常数吧。

code:

typedef vector<int> poly;
poly F,G[N];
void build(int root,int l,int r){
if(l==r){
G[root].clear();
G[root].push_back(P-a[l]),G[root].push_back(1);
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid),build(root<<1|1,mid+1,r);
G[root]=G[root<<1]*G[root<<1|1];
}
void calc(int root,int l,int r,poly now){
if(l==r)
{ans[l]=now[0];return;}
int mid=(l+r)>>1;
calc(root<<1,l,mid,now%G[root<<1]);
calc(root<<1|1,mid+1,r,now%G[root<<1|1]);
}

多项式快速插值

前置知识 $1$：拉格朗日插值

给定 $(n+1)$ 个点 $(x_i,y_i)$，其中每个 $x$ 互不相同，那么存在唯一的次数不超过 $n$ 的多项式 $f(x)$，满足 $\forall i\in [1,n]$， $f(x_i)=y_i$，即：

$$f(x)=\sum _{i=1}^n{y}_i\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}$$

这个应该比较显然，因为对于 $x_k$，只有当上式中 $i=k$ 时 ${\prod }_{j\ne i}\frac{x-x_j}{x_i-x_j}=1$，否则是 $0$。

前置知识 $2$：洛必达法则

若 $\underset{x\to a}{\lim }f(x)=0$， $\underset{x\to a}{\lim }g(x)=0$，在点 $a$ 的某去心邻域内两者都可导，且 $g^{\prime }(x)\ne 0$，那么有：

$$\underset{x\to a}{\lim }\frac{f(x)}{g(x)}=\underset{x\to a}{\lim }\frac{f^{\prime }(x)}{g^{\prime }(x)}$$

接下来回到我们的问题。

problem:

给出 $n$ 个点 $(x_i,y_i)$，求一个 $n-1$ 次的多项式 $f(x)$，使得 $f(x_i)\equiv y_i(\mathrm{m}\mathrm{o}\mathrm{d}998244353)$。

solution:

考虑到直接用求拉格朗日插值是 $O(n^2)$ 的，我们把它变一下形：

$$f(x)=\sum _{i=1}^n\frac{y_i}{{\prod }_{j\ne i}(x_i-x_j)}\prod _{j\ne i}(x-x_j)$$

考虑先求出 $G={\prod }_{j\ne i}(x_i-x_j)$。

令 $g(x)={\prod }_{j=1}^n(x-x_j)$，那么 $j\ne i$ 的限制就相当于除了个 $x-x_i$，所以 $G=\frac{g(x_i)}{x-x_i}$。

发现这时分子分母都是 $0$，根据洛必达法则，有 $G=\frac{g^{\prime }(x_i)}{1}=g^{\prime }(x_i)$。

接下来考虑分治优化，设 $f_{l,r}$ 表示 $[l,r]$ 的答案，$mid=\lfloor \frac{l+r}{2}\rfloor$，那么有：

$$\begin{array}{rl}{f}_{l,r}& =\sum _{i=l}^r\frac{y_i}{g^{\prime }(x_i)}\prod _{j=l}^r[j\ne i](x-x_j)\\ & =\prod _{k=mid+1}^r(x-x_k)\sum _{i=l}^{mid}\frac{y_i}{g^{\prime }(x_i)}\prod _{j=l}^{mid}[j\ne i](x-x_j)+\prod _{k=l}^{mid}(x-x_k)\sum _{i=mid+1}^r\frac{y_i}{g^{\prime }(x_i)}\prod _{j=mid+1}^r[j\ne i](x-x_j)\\ & =f_{l,mid}\prod _{k=mid+1}^r(x-x_k)+f_{mid+1,r}\prod _{k=l}^{mid}(x-x_k)\end{array}$$

其实就是把 $f_{l,r}$ 拆成 $f_{l,mid}$ 和 $f_{mid+1,r}$ 的式子。

然后用分治$ntt$预处理出 $g$，然后多点求值求 $g^{\prime }(x_i)$，最后分治求 $f_{1,n}$ 即可。

时间复杂度 $O(n\log n)$。

code:

PS: $h$ 数组就是事先处理出的 $\frac{y_i}{g^{\prime }(x_i)}$。

poly Get(int root,int l,int r){
if(l==r)
return poly(1,h[l]);
int mid=(l+r)>>1;
poly L=Get(root<<1,l,mid),R=Get(root<<1|1,mid+1,r);
return L*G[root<<1|1]+R*G[root<<1];
}

下降幂多项式乘法

problem:

给定一个 $n$ 次下降幂多项式 $A(x)$ 和 $m$ 次下降幂多项式 $B(x)$，你要求出一个 $(n+m)$ 次下降幂多项式 $F(x)$ 满足 $F(x)=A(x)B(x)$。

solution:

首先有一个重要的结论，即：

$$e^x=\sum _{i=0}^{\infty }\frac{x^i}{i!}$$

这个根据 $e^x$ 在 $0$ 处泰勒展开即可得到。

考虑对于 $x^{\underline{n}}$ 构建 EGF：

$$\begin{array}{rl}{x}^{\underline{n}}& =\sum _{i=n}^{\infty }\frac{i^{\underline{n}}}{i!}{x}^i\\ & =\sum _{i=n}^{\infty }\frac{1}{(i-n)!}{x}^i\\ & =\sum _{i=n}^{\infty }\frac{x^{i-n}}{(i-n)!}{x}^n\\ & =x^n{e}^x\end{array}$$

考虑对于 $f(x)={\sum }_{i=0}^{\infty }{a}_i{x}^{\underline{i}}$ 的点值构造 EGF：

$$\begin{array}{rl}g(x)& =\sum _{i=0}^{\infty }\frac{f(i)}{i!}{x}^i\\ & =\sum _{i=0}^{\infty }\frac{x^i}{i!}\sum _{j=0}^{\infty }{a}_j{i}^{\underline{j}}\\ & =\sum _{j=0}^{\infty }{a}_j\sum _{i=0}^{\infty }\frac{i^{\underline{j}}}{i!}{x}^i\\ & =\sum _{j=0}^{\infty }{a}_j{x}^j{e}^x\\ & =e^x\sum _{i=0}^{\infty }{a}_i{x}^i\end{array}$$

因此只需要用普通多项式的系数卷个 $e^x$ 就得到了点值的 EGF。

点值还原原多项式也只需要卷个 $e^{-x}$。

代码很简单，就是之前的操作，就不放了。

最后

以上就是小巧帆布鞋最近收集整理的关于多项式各种操作的全部内容，更多相关多项式各种操作内容请搜索靠谱客的其他文章。