已经吃撑了
多项式求逆
对于多项式 \(A(x)\) ，求多项式 \(B(x)\)， 满足 \(A(x) * B(x) \equiv 1 \pmod{x^n}\)。
递归求解。
求模 \(x^n\) 的逆元时，假设先求出了模 \(x^{\lceil\frac{n}{2}\rceil}\) 的逆元。
设模 \(x^n\) 逆元为 \(B\)，模 \(x^{\lceil\frac{n}{2}\rceil}\) 逆元为 \(B'\)，则：
\[A*B'\equiv 1\pmod {x^{\lceil\frac{n}{2}\rceil}} \]且
\[A*B\equiv 1\pmod {x^{\lceil\frac{n}{2}\rceil}} \]所以
\[B'-B\equiv 0\pmod {x^{\lceil\frac{n}{2}\rceil}} \]\[(B'-B)^2\equiv 0\pmod {x^n} \]\[B'^2-2BB'+B^2\equiv 0\pmod {x^n} \]\[AB'^2-2B'+B\equiv 0\pmod {x^n} \]\[B\equiv 2B'-AB'^2\pmod {x^n} \]然后就可以从下往上递推了,注意边界
一个加速的技巧是把 \(B'\) 和 \(A'\) 转成点值表达式后直接算出 \(B'\) 的点值表达式，这样可以减少NTT的次数，显著提高效率(指7000ms-->1000ms)
求逆
void inverse(int *A,int *B,int n){
static int a[M],b[M];
b[0]=qpow(A[0],Mod-2,Mod);
int bas=2;
while(bas<=2*n){
for(int i=0;i<bas;i++) a[i]=A[i];
int len=init(bas+bas-2);
NTT(b,len,1);NTT(a,len,1);
for(int i=0;i<len;i++) b[i]=(1ll*b[i]*2%Mod-1ll*a[i]*b[i]%Mod*b[i]%Mod+Mod)%Mod;
NTT(b,len,-1);
for(int i=bas;i<len;i++) b[i]=0;
bas<<=1;
}
for(int i=0;i<bas;i++) B[i]=b[i];
for(int i=0;i<bas;i++) a[i]=b[i]=0;
}
多项式开根
对于一个 \(n-1\) 次多项式 \(F(x)\)，求一个在 \({} \bmod x^n\) 意义下的多项式 \(G(x)\)，使得 \(G^2(x) \equiv F(x) \pmod{x^n}\)。若有多解，请取零次项系数较小的作为答案。
设 \(H^2(x)\equiv F(x)(mod\ x^{\lceil\frac n2 \rceil})\)
有：
\[G(x)\equiv H(x)(mod\ x^{\lceil\frac n2 \rceil}) \]\[G(x)-H(x)\equiv 0(mod\ x^{\lceil\frac n2 \rceil}) \]\[(G(x)-H(x))^2\equiv 0(mod\ x^{\lceil\frac n2 \rceil}) \]\[G^2(x)-2H(x)*G(x)+H^2(x)\equiv 0(mod\ x^n) \]\[F(x)-2H(x)*G(x)+H^2(x)\equiv 0(mod\ x^n) \]\[G(x)=\frac {F(x)+H^2(x)}{2H(x)} \]同样可以递推实现
开根
void Sqrt(int *A,int *B,int n){
static int a[M],b[M],revb[M];
b[0]=1;
int bas=2;
while(bas<=2*n){
for(int i=0;i<bas;i++) a[i]=A[i];
inverse(b,revb,bas-1);
Mul(revb,a,a,bas-1,bas-1);
for(int i=0;i<bas;i++) b[i]=1ll*add(a[i],b[i])*inv2%Mod;
bas<<=1;
}
for(int i=0;i<bas;i++) B[i]=b[i];
for(int i=0;i<bas;i++) a[i]=b[i]=revb[i]=0;
}
多项式求导
求多项式 \(F(x)\) 的导数 \(F'(x)\)
因为
\[f(x)=x^n \\ f'(x)=nx^{n-1} \]所以
\[F'(x)=\sum_{i=0}^{n}a_{i+1}(i+1)x^i \]求导
void Dao(int *A,int *B,int n){
for(int i=1;i<=n;i++) B[i-1]=1ll*A[i]*i%Mod;
B[n]=0;
}
多项式求不定积分
求多项式 \(F(x)\) 的不定积分 \(G(x)\)
因为
\[\int x^adx=\frac{1}{a+1}x^{a+1} \]所以
\[G(x)=\sum_{i=1}^{n}\frac{a_{i-1}}{i} \\ \]积分(暗藏玄只因)
void Zhiyin(int *A,int *B,int n){
for(int i=1;i<=n;i++) B[i]=1ll*A[i-1]*qpow(i,Mod-2,Mod)%Mod;
B[0]=0;
}
多项式求Ln
给出 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\)，满足 \(B(x) \equiv \ln A(x)\).
为了这个学了导数
\[B(x)=F(A(x)),F(x)=ln(x) \]因为\(F'(x)=\frac{1}{x}\)
所以
\[B'(x)=F'(A(x))A'(x)=\frac{A'(x)}{A(x)} \]所以对 \(A\) 求导再求逆再乘起来再积回去就行了
求Ln
void Ln(int *A,int *B,int n){
static int a[M],b[M];
Dao(A,a,n);
inverse(A,b,n);
Mul(a,b,a,n,n);
Zhiyin(a,B,n);
}
多项式求exp
给出 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\)，满足 \(B(x) \equiv \text e^{A(x)}\)。
咕了，要用到泰勒展开和牛顿迭代，什么时候看懂了再补过程
求exp
void Exp(int *A,int *B,int n){
if(n==0) return B[0]=1,void();
static int f[M];
Exp(A,B,n>>1);
Ln(B,f,n);
f[0]=minu(A[0]+1,f[0]);
for(int i=1;i<=n;i++) f[i]=minu(A[i],f[i]);
Mul(f,B,B,n,n);
}