多项式算法集
小菜鸟
2019-03-23 22:33:38
未完成，留坑待填
先放代码和部分推导过程
### 多项式求逆
给定$F(x)$，求$G(x)$满足$F(x)G(x)\equiv 1(\mod x^n)$
（以下省略多项式的$(x)$）
假设已经求出一个$H$满足$FH\equiv 1(\mod x^{\lceil\frac{n}{2}\rceil})$
同时，显然$FG \equiv 1 (\mod x^{\lceil\frac{n}{2}\rceil})$
于是得$FH-FG\equiv 0(\mod x^{\lceil\frac{n}{2}\rceil})$
两边平方得$F^2G^2 - 2F^2GH + F^2H^2\equiv 0(\mod x^{n})$
注意为什么可以把$\lceil\frac{n}{2}\rceil$变成$n$
显然$x\equiv 0(\mod P)$意味着$P$是$x$的因数或因式
那么显然，$P^2$也应该是$x^2$的因数或因式
回到推导过程
由于$FG\equiv 1(\mod x^n)$
消去部分$FG$得
$FG-2FH+F^2H^2\equiv 0(\mod x^n)$
同除$F$并移项得$G\equiv 2H-FH^2(\mod x^n)$
由此我们得到倍增求逆的方法
初始只要求出$F$常数项的逆元作为$H$即可，不断迭代或递归倍增。
### 多项式对数函数
我们知道$\frac{d(\ln x)}{dx}=x^{-1}$
多项式同理，然后积分积回去即可
### 多项式牛顿迭代
作为后面各种玩意的基础做一个证明
对于无限可导函数$f(F)$
根据泰勒级数可展开为$f(F)=f(F_0)+f'(F_0)(F-F_0)+\cdot\cdot\cdot$
当我们要求出函数零点$F$使得$f(F)\equiv 0 (\mod x^{n})$时
同样假设有$F_0$满足$f(F_0)\equiv 0 (\mod x^{\lceil\frac{n}{2}\rceil})$
则$F-F_0\equiv0(\mod x^{\lceil\frac{n}{2}\rceil})$
同求逆时的推理，由于无穷级数后面的项均包含$(F-F_0)^k(k\geqslant2)$
所以后面的项在$(\mod x^n)$意义下必定为零，可以忽略
于是此时得到$f(F)=f(F_0)+f'(F_0)(F-F_0)(\mod x^n)$
要求$f(F)$的零点，故将$f(F)\equiv 0(\mod x^n)$代入后移项
得$F \equiv F_0-\frac{f(F_0)}{f'(F_0)}(\mod x^n)$
同多项式求逆的思路，倍增即可
### 多项式指数函数
给出$F$，求$e^F (\mod x^n)$
容易发觉就是求$Ln(G)\equiv F (\mod x^n)$的解
移项，牛顿迭代即可
要求$F$常数项必须为$0$，否则无法得出合适的$F_0$，迭代出来没有意义
### 多项式幂函数
（洛谷有指数是常数的模板，会被倍增快速幂艹过去，此处给出指数是多项式的解法）
我们知道$x^y=e^{y \ln x}$
多项式同理，$F^G=e^{G\,Ln\,F}$，直接套板子
但我们又发现当$F$常数项不为$1$时不可做
此时若常数项为$0$，就先将整个多项式乘$x^{-len}$使得常数项非零
然后把整个多项式除一个常数项$F[0]$，那么常数项就变成了$1$
用正常方法求出后乘上$(F[0]x^{len})^k$即可
### 多项式三角函数
根据欧拉公式$e^{i\theta}=\cos\theta+i\sin\theta$
得出三角函数定义域扩展到复数时的形式
$sin\theta=\frac{e^{i\theta}-e^{-i\theta}}{2}$
$cos\theta=\frac{e^{i\theta}+e^{-i\theta}}{2}$
~~有没有觉得眼熟好像见过~~
既然复数可以，多项式当然也可以！
但注意到$i$是个棘手的玩意
我们知道$i^2=-1$
那么$i^2\equiv 998244352 (\mod 998244353)$
发现恰有二次剩余为$86583718$或$911660635$
取一者（一般取较小者为正）带入即可。
### 多项式反三角函数
~~你一定以为要牛顿迭代吧~~
然而参考对数函数，求导，积分，完。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int P=998244353,g=3,gi=332748118,inv2=499122177;
const int imag_i=86583718,inv2i=954952494;
int power(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=(long long)res*a%P;
b>>=1;
a=(long long)a*a%P;
}
return res;
}
int rev[1<<18];
void getrev(int n)
{
int bit=1;
while(1<<bit<n)++bit;
for(int i=1;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}
void ntt(int *a,int n,int dft)
{
for(int i=0;i<n;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int step=1;step<n;step<<=1)
{
const int wn=power(dft==1?g:gi,(P-1)/(step<<1));
for(int j=0;j<n;j+=step<<1)
{
int wnk=1;
for(int k=j;k<j+step;++k)
{
const int x=a[k];
const int y=(long long)a[k+step]*wnk%P;
a[k]=(x+y)%P;
a[k+step]=(x-y+P)%P;
wnk=(long long)wnk*wn%P;
}
}
}
if(dft==-1)
{
const int inv=power(n,P-2);
for(int i=0;i<n;++i)
{
a[i]=(long long)a[i]*inv%P;
}
}
}
void copy(int *a,int *b,int n)
{
for(int i=0;i<n;++i)b[i]=a[i];
}
void add(int *a,int *b,int *c,int n)
{
for(int i=0;i<n;++i)
{
c[i]=(a[i]+b[i])%P;
}
}
void add(int *a,int b,int *c,int n)
{
for(int i=0;i<n;++i)
{
c[i]=(a[i]+b)%P;
}
}
void dec(int *a,int *b,int *c,int n)
{
for(int i=0;i<n;++i)
{
c[i]=(a[i]-b[i]+P)%P;
}
}
void dec(int *a,int b,int *c,int n)
{
for(int i=0;i<n;++i)
{
c[i]=(a[i]-b+P)%P;
}
}
void mul(int *a,int *b,int *c,int n)
{
n<<=1;
getrev(n);
ntt(a,n,1);
if(a!=b)ntt(b,n,1);
for(int i=0;i<n;++i)
{
c[i]=(long long)a[i]*b[i]%P;
}
ntt(a,n,-1);
if(a!=b)ntt(b,n,-1);
if(a!=c&&b!=c)ntt(c,n,-1);
}
void mul(int *a,int b,int *c,int n)
{
for(int i=0;i<n;++i)
{
c[i]=(long long)a[i]*b%P;
}
}
int temp[1<<18];
void __inv(int *a,int *b,int n)
{
if(n==1)
{
b[0]=power(a[0],P-2);
return;
}
__inv(a,b,n>>1);
getrev(n<<1);
for(int i=0;i<n;++i)temp[i]=a[i];
for(int i=n;i<n<<1;++i)temp[i]=0;
ntt(b,n<<1,1);
ntt(temp,n<<1,1);
for(int i=0;i<n<<1;++i)
{
b[i]=(2-(long long)b[i]*temp[i]%P+P)%P*b[i]%P;
}
ntt(b,n<<1,-1);
for(int i=n;i<n<<1;++i)b[i]=0;
}
void inv(int *a,int *b,int n)
{
memset(temp,0,sizeof(temp));
__inv(a,b,n);
}
void derivative(int *a,int *b,int n)
{
for(int i=0;i<n;++i)b[i]=(long long)a[i+1]*(i+1)%P;
}
void integration(int *a,int *b,int n)
{
for(int i=n;i>0;--i)b[i]=(long long)a[i-1]*power(i,P-2)%P;
b[0]=0;
}
int temp2[1<<18];
void ln(int *a,int *b,int n)
{
memset(temp2,0,sizeof(temp2));
inv(a,temp2,n);
derivative(a,b,n);
mul(temp2,b,temp2,n);
integration(temp2,b,n-1);
}
int temp3[1<<18],temp4[1<<18];
void exp(int *a,int *b,int n)
{
memset(temp3,0,sizeof(temp3));
memset(temp4,0,sizeof(temp4));
int len=1;
b[0]=1;
while(len<n)
{
len<<=1;
ln(b,temp3,len);
dec(temp3,a,temp3,len);
mul(b,temp3,temp4,len);
dec(b,temp4,b,len);
}
}
int temp5[1<<18];
void sqrt(int *a,int *b,int n)
{
memset(temp5,0,sizeof(temp5));
ln(a,temp5,n);
for(int i=0;i<n;++i)temp5[i]=(long long)temp5[i]*inv2%P;
exp(temp5,b,n);
}
void pow(int *a,int k,int *b,int n)
{
memset(temp5,0,sizeof(temp5));
ln(a,temp5,n);
for(int i=0;i<n;++i)temp5[i]=(long long)temp5[i]*k%P;
exp(temp5,b,n);
}
int temp6[1<<18],temp7[1<<18],temp8[1<<18];
void sin(int *a,int *b,int n)
{
memset(temp5,0,sizeof(temp5));
memset(temp6,0,sizeof(temp6));
memset(temp7,0,sizeof(temp7));
memset(temp8,0,sizeof(temp8));
mul(a,imag_i,temp5,n);
mul(a,P-imag_i,temp6,n);
exp(temp5,temp7,n);
exp(temp6,temp8,n);
dec(temp7,temp8,temp7,n);
mul(temp7,inv2i,b,n);
}
void cos(int *a,int *b,int n)
{
memset(temp5,0,sizeof(temp5));
memset(temp6,0,sizeof(temp6));
memset(temp7,0,sizeof(temp7));
memset(temp8,0,sizeof(temp8));
mul(a,imag_i,temp5,n);
mul(a,P-imag_i,temp6,n);
exp(temp5,temp7,n);
exp(temp6,temp8,n);
add(temp7,temp8,temp7,n);
mul(temp7,inv2,b,n);
}
int temp9[1<<18],temp10[1<<18];
void tan(int *a,int *b,int n)
{
memset(temp9,0,sizeof(temp9));
sin(a,temp8,n);
cos(a,temp9,n);
inv(temp9,temp10,n);
mul(temp8,temp10,b,n);
}
```