多项式全家桶学习
多项式乘法
用DFT将系数表达式转为点值表达式，(O(n))乘法，再IDFT回去即可
多项式求逆
给定多项式(A(x))，求(B(x))满足(A(x)B(x)equiv1(mod x^n))
考虑倍增
不妨假设(n=2^k)
- 当(n=1)时，(B(x)=A(x)^{p-2})
- 当(n>1)时，已有(A(x)B'(x)equiv1(mod x^{frac{n}{2}}))
[A(x)B(x)equiv1(mod x^n)
]
显然有
[A(x)B(x)equiv1(mod x^{frac{n}{2}})
]
又因为
[A(x)B'(x)equiv1(mod x^{frac{n}{2}})
]
则
[A(x)(B(x)-B'(x))equiv1(mod x^{frac{n}{2}})
]
所以
[B(x)-B'(x)equiv 0(mod x^{frac{n}{2}})
]
前n/2项都为0，那么平方后就有
[B(x)^2-2B(x)B'(x)+B'(x)^2equiv0(mod x^n)
]
两边同乘(A(x))，整理，有
[B(x)equiv2B'(x)+A(x)B'(x)^2(mod x^n)
]
递归/自下而上递推即可
多项式求导、积分
求导
[frac{mathbb{d}(sumlimits_{k=0}^{n-1}a_k x^k)}{mathbb{d} x}=sum_{k=0}^{n-1}frac{mathbb{d}(a_k x^k)}{mathbb{d} x}=sum_{k=1}^{n-1}k a_k x^{k-1}=sum_{k=0}^{n-2}(k+1)a_{k+1}x^k
]
积分
[intsum_{k=0}^{n-1}a_k x^k mathbb{d}x=sum_{k=0}^{n-1}int a_k x^kmathbb{d}x=sum_{k=0}^{n-1}frac{a_k}{k+1}x^{k+1}=sum_{k=1}^nfrac{a_{k-1}}{k}x^k
]
多项式求ln
已知(A(x))，求(B(x)=ln(A(x)))
对两边求导，得到
[B'(x)=frac{A'(x)}{A(x)}
]
两边积分，则有
[B(x)=B(x)=intfrac{A'(x)}{A(x)}mathbb{d}x
]
求导+积分+求逆解决