多项式全家桶
$\ \ \ \ \ \ \,$终于把多项式差不多弄完了，可以找个机会在退役前把多项式整理封装弄好，也算是留下了一点东西吧（嘿嘿。
$\ \ \ \ \ \ \,$这一部分实例的代码是用 $std::vector$ 封装好的：
2022-02-14 跟新：把这最长的一篇搬来新博客上面，然后做了一下整合
基础
定义
$\ \ \ \ \ \ \,$多项式（Polynomial）是代数学中的基础概念，是由称为未知数的变量和称为系数的常数通过有限次加减法、乘法以及自然数幂次的乘方运算得到的代数表达式。多项式是整式的一种。未知数只有一个的多项式称为一元多项式。
$\ \ \ \ \ \ \,$一个$n$元多项式，也就是长度为$n$的多项式$f$，我们可以这样表达：
$f=\sum_{i=0}^{n}f_i\cdot x^i$
$\ \ \ \ \ \ \,$我们一般简写为:
$f=\sum_{i=0}^{n}f_i$
$\ \ \ \ \ \ \,$首先是可能需要用到的模板定义，都是比较基础的数论知识，不赘述了：1
2
3
4
5
6
7
8
9
10
11
12
13
14
//封装多项式为 std::vector，方便resize等操作
void print(Polynomial &a,int len){for(int i=0;i<len;i++)printf("%d ",a[i]);}
const int mod=998244353,mod_g=3,img=86583718;
//mod为多项式系数的取模值，mod_g是它的原根，img为在模意义下的虚部，只有多项式三角函数会遇到。
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void exgcd(int a,int b,int &x,int &y){
if(!b){x=1;y=0;return;}
exgcd(b,a%b,y,x);y-=x*(a/b);
}
//gcd，exgcd只有在开根的时候会用到
int power(int a,int b)
{int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;}
NTT
$\ \ \ \ \ \ \,$然后是核心的快速数论变换 $NTT$，相关请看【求多项式卷积的变换】：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24Polynomial R;
inline int Binary_Rounding(const int &n)
{int len=1;for(;len<n;len<<=1);return len;}
//二进制向上取整，为方便NTT变换准备。
inline int Prepare_Transformation(int n){
int L=0,len;for(len=1;len<n;len<<=1)L++;R.clear();R.resize(len);
for(int i=0;i<len;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
return len;
}
//预处理R数组，准备变换，在每次NTT之前理论都要调用此函数。
void NTT(Polynomial &a,int f){
int n=a.size();
for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
for(int i=1;i<n;i<<=1)
for(int j=0,gn=power(mod_g,(mod-1)/(i<<1));j<n;j+=(i<<1))
for(int k=0,g=1,x,y;k<i;k++,g=1ll*g*gn%mod)
x=a[j+k],y=1ll*g*a[i+j+k]%mod,
a[j+k]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
if(f==-1){
reverse(a.begin()+1,a.end());
int inv=Inv(n);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
}
}
多项式的加，减，卷积
$\ \ \ \ \ \ \,$对于一个长度为$n$的多项式$f$和长度为$m$的多项式$g$:
$\begin{aligned}f+g&=\sum_{i=0}^{n}f_i+\sum_{i=0}^{m}g_i\\ &=\sum_{i=0}^{max(n,m)}f_i+g_i\end{aligned}$
$\begin{aligned}f-g&=\sum_{i=0}^{n}f_i-\sum_{i=0}^{m}g_i\\ &=\sum_{i=0}^{max(n,m)}f_i-g_i\end{aligned}$
$\ \ \ \ \ \ \,$多项式的卷积，我们还是对于上文中的两个函数$f$和$g$，这个地方不展开写挺不方便的，我们就展开吧：
$\begin{aligned}f\bigotimes g&=\sum_{i=0}^{n}f_i\cdot x^i\times \sum_{i=0}^{m}g_i\cdot x^i \\ &=\sum_{v=0}^{n+m}f_b\cdot x^b\times g_a\cdot x^a[a+b=v]\\&=\sum_{x=0}^{n+m}\sum_{i=0}^{v}f_i\cdot g_{v-i}\cdot x^v\end{aligned}$
$\ \ \ \ \ \ \,$计算的复杂度呢，是$O(n^2)$的，可以用一些神奇算法优化成$O(n\log n)$的具体看这里：【求多项式卷积的变换】
$\ \ \ \ \ \ \,$多项式的加，减，卷积，是比较基本的多项式操作，以模拟和 $NTT$ 为主，主要是展示和记录模板的操作。
$\ \ \ \ \ \ \,$ 单项式其实就是常数。
多项式加，减单项式
1 | inline Polynomial operator +(const Polynomial &a,const int &b){ |
多项式卷积单项式
1 | inline Polynomial operator *(const Polynomial &a,const int &b){ |
多项式加，减多项式
$\ \ \ \ \ \ \,$注意 $vector$ 在赋值之前，一定先要 $resize$ 到合适的位置，不然就会一直 $RE$ 了。
1 | inline Polynomial operator +(const Polynomial &a,const Polynomial &b){ |
多项式卷积多项式
$\ \ \ \ \ \ \,$P3803 【模板】多项式乘法（FFT）（可以NTT过
1 | inline Polynomial operator *(const Polynomial &a,const Polynomial &b){ |
多项式除法和取模
$\ \ \ \ \ \ \,$你问我多项式除法（P4512 【模板】多项式除法）？？？多项式除法滚出多项式全家桶！！！（超凶
$\ \ \ \ \ \ \,$看了下一篇 求逆 过后，应该可以自己完成多项式除法了，但是在很多小地方……容易自闭。
$\ \ \ \ \ \ \,$还是贴一下板子吧，小心别一开始二进制取整了：
1 | inline Polynomial operator /(const Polynomial &a,const Polynomial &b){ |
多项式的逆，导，积
$\ \ \ \ \ \ \,$这一部分麻烦一点了，但是很重要，几乎所有多项式都得用的，不过好在也不是很复杂的。
多项式求逆
$\ \ \ \ \ \ \,$P4238 【模板】多项式求逆
$\ \ \ \ \ \ \,$求一个多项式 $A$ 的模 $x^n$ 的逆元$B$ 时，假设先求出了模$x^{\frac{n}{2}}$ 的逆元 $B’$，既：
$A*B’ \equiv 1\ (mod\ x^{\frac{n}{2}})$
$A*B \equiv 1\ (mod\ x^{n})$
$\ \ \ \ \ \ \,$那么显然存在：
$AB \equiv 1\ (mod\ x^{\frac{n}{2}})=AB’$
$B-B’ \equiv 0\ (mod\ x^{\frac{n}{2}})$
$\ \ \ \ \ \ \,$两边同时平方：
$B^2-2BB’+B’^2 \equiv 0\ (mod\ x^n)$
$\ \ \ \ \ \ \,$再把 $A$ 乘回去：
$(AB)B-(AB)2B’+AB’^2 \equiv A0\ (mod\ x^n)$
$B-2B’+A*B’^2 \equiv 0\ (mod\ x^n)$
$B \equiv 2B’-A*B’^2\ (mod\ x^n)$
$\ \ \ \ \ \ \,$我们就可以倍增来处理它了，起点是$B_0 \equiv A_0^{-1}(mod\ x^1)$
1 | inline Polynomial Inverse(const Polynomial &a){ |
多项式求导
$\ \ \ \ \ \ \,$按照公式来，公式挺简单的，设多项式 $A$ 的导数为 $A’$。
$\ \ \ \ \ \ \,$那么有：
$x^{A’}=Ax^{A-1}$
$\ \ \ \ \ \ \,$既：
$A’_{i}=i\times A_{i+1}$
1 | inline Polynomial Derivation(const Polynomial &a){ |
多项式求积
$\ \ \ \ \ \ \,$还是按照公式来，设多项式 $A$ 的积分为 $A’$。
$\ \ \ \ \ \ \,$那么有：
$\int x^{A’}dx=\frac{1}{A+1}x^{A-1}$
$\ \ \ \ \ \ \,$既：
$A’_{i}=\frac{A_{i-1}}{i}$
$\ \ \ \ \ \ \,$那就是乘逆元咯 （兄弟俩长得挺像
1 | inline Polynomial Integral(const Polynomial &a){ |
多项式复合逆
$\ \ \ \ \ \ \,$NFLSOJ #332. 多项式复合逆
$\ \ \ \ \ \ \,$对于一个多项式$F$，若是存在一个多项式$G$，使得：
$G(F(x))=x$
$\ \ \ \ \ \ \,$那么就称多项式$G$是多项式$F$的复合逆。
$\ \ \ \ \ \ \,$目前复合逆没有$O(n \log n)$的做法，但是可以用拉格朗日反演做到$O(n^2 \log n)$，既每一项每一项得求，求一项的时间是$O(n \log n)$的，下面给出公式：
$G_i=\frac{\left(\frac{x}{F}\right)^i_{i-1}}{i}$
$\ \ \ \ \ \ \,$那么求逆和卷积就好了，$x$都挺好处理的，证明很复杂，感兴趣可以看这里。
$\ \ \ \ \ \ \,$有一个值得注意的地方就是求逆的时候，应该直接求$\frac{F}{x}$的逆，而不是$F$的逆，因为既然多项式 $F$ 存在复合逆，那么常数项就应该是 $0$ ，这是不可能求逆的，先算出$\frac{F}{x}$即可。
$\ \ \ \ \ \ \,$若是需要$O(n \log n)$只求一项，则需要用到快速幂，下一篇我们会讲到
1 | inline Polynomial Composition_Inverse(const Polynomial &a){ |
多项式的ln，exp
$\ \ \ \ \ \ \,$对数和指数是很重要的东西了，复杂的多项式都和他们有关系，所以说掌握很重要，这里不建议光背板子，因为这两个板子都有致命的限制，而在实际操作的时候，可以通过一些方法绕过这个限制直接求解，这个就很重要了。
多项式的$ln$
$\ \ \ \ \ \ \,$P4725 【模板】多项式对数函数
$\ \ \ \ \ \ \,$公式先走起咯：
$\ln(A)=\int \frac{A’}{A}dx$
$\ \ \ \ \ \ \,$观察公式，一句话解决：
$\ \ \ \ \ \ \,$导卷逆的积：
$\ \ \ \ \ \ \,$看上去很模板，当然模板也是很短的：
1 | inline Polynomial Logarithmic(const Polynomial &a){ |
$\ \ \ \ \ \ \,$还有一个值得注意的问题，一般求对数的多项式，是需要要求常数项为 $1$ 的，因为我们知道：
$e^0=1$
$\ \ \ \ \ \ \,$也就是：
$ln(1)=0$
$\ \ \ \ \ \ \,$这样算出来的 $ln$ 常数项是 $0$，而我们追后一步在算积的时候，是默认把常数项补上 $0$ 的，这样就没有问题。可要是原多项式常数项不为 $1$ 呢？
$\ \ \ \ \ \ \,$显然应该算积的时候在常数项补上 $ln(C)$ （C为常数项），不过这个数在模的意义下应该是多少呢？这个问题周道确实不能解决了，所以说，模板题的话，会给出这个常数项为 $1$的条件的。
$\ \ \ \ \ \ \,$否认常数项不等于$1$，完全不能求 $ln$ 的说法。
多项式的$exp$
$\ \ \ \ \ \ \,$这玩意说简单也简单，说复杂也挺复杂的，我们得引入一个新玩意，【牛顿迭代】，是求函数零点的玩意，收敛速度非常理想，我在这里有简略的讲过：【导数和牛顿迭代】，我也在洛谷出过一个牛顿迭代的裸题，感兴趣可以去体验一下牛顿迭代的神奇：【P4986 逃离】。
$\ \ \ \ \ \ \,$说远了，现在我们来康康怎么求指数函数。
$\ \ \ \ \ \ \,$令我们要求的是 $A$ 的指数函数 $B$，既是：
$B=e^A$
$\ \ \ \ \ \ \,$变形得：
$\ln(B)-A=0$
$\ \ \ \ \ \ \,$咦？$0$ ?，我们把多项式当做函数值看看？
$\ \ \ \ \ \ \,$哇，函数零点！马上牛顿迭代呀！
$\ \ \ \ \ \ \,$设$F(B)=\ln (B)-A$，我们要求 $F$的零点，根据牛顿迭代的公式可得（注意这里B后面的括号的迭代版本的意思，不是多项式的项）：
$B(x)=B(x-1)-\frac{F\left(B(x-1)\right)}{F’\left(B(x-1)\right)}$
$\ \ \ \ \ \ \,$而根据导数的定义，$F’(B)=\frac{1}{B}$，（【导数和牛顿迭代】里面有提到过一点，这里是把$A$当做常数舍去了）
$\ \ \ \ \ \ \,$那我们现在把牛顿迭代的公式化简：
$\begin{aligned}
B(x)&
=B(x-1)-F\left(B(x-1)\right)\times B(x-1)\\&
=B(x-1)-B(x-1)\times F\left(B(x-1)\right)\\&
=B(x-1)-B(x-1)\times \left(\ln \left(B(x-1)\right)-A\right)\\&
=B(x-1)\times \left(1-\ln \left(B(x-1)\right)+A \right)
\end{aligned}$
$\ \ \ \ \ \ \,$再次强调B后面的括号的迭代版本的意思，不是多项式的项。
$\ \ \ \ \ \ \,$现在看似分治可做，我们用两个容器相互装版本。每次老版本一卷，新版本长度就会倍增，所以说我们做 $\log n$ 次迭代就好。我们的操作相当于把式子拆了求收敛值，所以不会有精度的问题，求出来就好了。
$\ \ \ \ \ \ \,$那么现在的问题是，第一个版本是怎么样，洛咕模板给的是保证 $A_0=0$，因为$e^0=1$，也就是$exp(0)=1$，所以说 $B_0=1$，也就是常数项为 $1$。
$\ \ \ \ \ \ \,$当然了，同理，他一般会保证$A_0=0$，我们不方便找到其他$exp(A_0)$模的意义下的值。如果可以算的话，可以在模板里面传入 $Constant$ 也就是 $exp(A_0)$ 的值。
$\ \ \ \ \ \ \,$否认$A_0$不等于$0$，完全不能求 $exp$ 的说法。
1 | inline Polynomial Exponential(const Polynomial &a,int Constant=1){ |
多项式快速幂，开方
$\ \ \ \ \ \ \,$这是多项式的大头了，实际使用多项式的$ln$和$exp$，这里呢，也只讲$ln$和$exp$的做法。
多项式快速幂
$\ \ \ \ \ \ \,$P5245 【模板】多项式快速幂
$\ \ \ \ \ \ \,$P5273 【模板】多项式幂函数 (加强版)
$\ \ \ \ \ \ \,$已知：
$A^k=exp\left(ln(A)\times k\right)$
$\ \ \ \ \ \ \,$显然求$ln$和$exp$就可以出答案了。
$\ \ \ \ \ \ \,$既然要求$ln$和$exp$，那么一定要考虑的是常数项的问题，洛谷的常规题面有保证 $a_0=1$，所以说无脑套模板就对了。
$\ \ \ \ \ \ \,$那么加强版没有保证 $a_0=1$，我们如何算常数项呢？
$\ \ \ \ \ \ \,$容易知道，$ln$的常数项为 $ln(a_0)$ ，$exp$的常数项是$exp(ln(a_0)\times k)$。好像算不出来呢。
$\ \ \ \ \ \ \,$可是$A^k=exp\left(ln(A)\times k\right)$，所以说$exp$的常数项是就应该是$A^k$的常数项，既 $a_0^k$ 。
$\ \ \ \ \ \ \,$所以说我们直接知道$exp$的常数项了，就不管他$ln$的常数项啦。
$\ \ \ \ \ \ \,$注意当$a[0]=0$时，常数项也应该是$B_0=0$，可是……常数项真的可以为$0$吗？
$\ \ \ \ \ \ \,$我们是要求 $F’(B)=\frac{1}{B}$ 的，分母当然不能为 $0$ 了，所以说我们还是要单独处理 $a[0]=0$ 的情况的。
$\ \ \ \ \ \ \,$把为$0$的前缀提出来，然后算，最后在答案前面加上提出的长度乘上$k$个$0$即可，模板没有管这个，需要自己注意。
1 | inline Polynomial Power(const Polynomial &a,const int &K){ |
多项式开方
$\ \ \ \ \ \ \,$P5205 【模板】多项式开根
$\ \ \ \ \ \ \,$P5277 【模板】多项式开根 (加强版)
$\ \ \ \ \ \ \,$已知：
$\sqrt{A}=exp\left(\frac{ln(A)}{2}\right)$
$\ \ \ \ \ \ \,$同理，求$ln$后，常数项带入$\sqrt{A_0}$ 求 $exp$ 就可以出答案了，不是加强版的照样直接贴模板也可以。
$\ \ \ \ \ \ \,$那么求常数项就比较讲究了，我们要求的是$\sqrt{A_0}\% mod$，也就是 $A_0$ 在 $\% mod$ 意义下的二次剩余。
$\ \ \ \ \ \ \,$如果会二次剩余，可以$O(\log mod)$求，不行还可以$BSGS$花时间 $O(\sqrt{mod})$ 求，时间差别不大，就先不放代码了，代码放在下一个环节，同理常数项为 $0$ 的时候要特殊判断。
多项式开高次方
$\ \ \ \ \ \ \,$U67388 【模板】多项式开高次根
$\ \ \ \ \ \ \,$已知：
$\sqrt[k]{A}=exp\left(\frac{ln(A)}{k}\right)$
$\ \ \ \ \ \ \,$同理，求$ln$后，常数项带入$\sqrt[k]{A_0}$ 求 $exp$ 就可以出答案了，现在主要是说一下如何用$BSGS$ 求 $\sqrt[k]{A_0}\% mod$，高次剩余。
$\ \ \ \ \ \ \,$因为需要保证有逆元或者可以直接除，所以需要保证 $k|(mod-1)$，或者 $k$ 与 $mod-1$ 互质。
1 | inline int BSGS(int a,int b){ |
$\ \ \ \ \ \ \,$模板题是周道用P5273 【模板】多项式幂函数 (加强版)的板子出的数据，跑了一下应该没有问题，自己写也过了，感兴趣可以写一下。因为目前还不能保证完全的正确性，所以说没有计划申请加入题库。但是目前过开方，写过几道题，这代码还是没有问题的。欢迎$Hack$。
多项式三角函数，反三角函数
$\ \ \ \ \ \ \,$说好了，这个作用不大，主要是……过一下板子，赶时间的小朋友可以右上角叉叉了……
多项式$Sin$ & 多项式$Cos$
$\ \ \ \ \ \ \,$P5264 【模板】多项式三角函数
$\ \ \ \ \ \ \,$欧拉公式：
$e^{ix}=\cos x+i\sin x$
$\ \ \ \ \ \ \,$直接推公式：
$e^{-ix}=\cos x-i\sin x$
$\ \ \ \ \ \ \,$加减一下得到:
$2\cos x=e^{ix}+e^{-ix}$
$2i\sin x=e^{ix}-e^{-ix}$
$\ \ \ \ \ \ \,$所以有：
$\cos x=\frac{e^{ix}+e^{-ix}}{i}$
$\sin x=\frac{e^{ix}-e^{-ix}}{2i}$
$\ \ \ \ \ \ \,$用多项式$A$替换掉 $x$ 即可：
$\cos (A)=\frac{exp(i\cdot A)+exp(-i\cdot A)}{i}$
$\sin (A)=\frac{exp(i\cdot A)-exp(-i\cdot A)}{2i}$
$\ \ \ \ \ \ \,$多项式卷单项式，$exp$，求逆，多项式卷多项式就好了，现在问题是 $i$ 怎么搞：
$\ \ \ \ \ \ \,$已知 $i^2=-1$，所以说 $i$ 既是 $mod-1$ 在 $\%mod$意义下的二次剩余，显然可以预处理出来，前置和目录里面已经说的有了，既为$img$。
1 | inline Polynomial Sin(const Polynomial &a){ |
多项式$Asin$ & 多项式$Atan$
$\ \ \ \ \ \ \,$P5265 【模板】多项式反三角函数
$\ \ \ \ \ \ \,$这个东西比较麻烦啦，直接给公式咯，具体证明可以看教材：
$Asin(A)=\int \frac{A’}{\sqrt{1-A^2}}dx$
$Atan(A)=\int \frac{A’}{1+A^2}dx$
1 | inline Polynomial Asin(const Polynomial &a){ |