zcmimi's blog
avatar
zcmimi
2020-08-27 22:46:00

https://www.luogu.com.cn/blog/wucstdio/duo-xiang-shi-suan-fa-di-chang-shuo-wen-ti

https://www.luogu.com.cn/blog/user7035/duo-xiang-shi-zong-jie

http://zory.ink/posts/8c82

多项式模板集合

以下对应代码都可以在这里找到:

多项式模板集合

使用fft时提高精度:

  • 使用long double
  • sincos应改成std::sinstd::cos,cmath中的sin,cos获得的值为double

多项式乘法

快速傅里叶变换 FFT

快速数论变换 NTT

快速沃尔什变换 FWT

任意模数NTT(三模数)

最大的数为p^2\times \max(n,m) \le 10^{23},所以一般选3个模数即可

设模数为m_1,m_2,m_3

\begin{cases} x \equiv A \pmod{m_1}\\ x \equiv B \pmod{m_2}\\ x \equiv C \pmod{m_3} \end{cases}

合并前两个:

A+k_1m_1=B+k_2m_2\\ A+k_1m_1\equiv B \pmod{m_2}\\ k_1\equiv \frac{B-A}{m_1} \pmod{m_2}

求出k_1,那么x\equiv A+k_1m_1 \pmod{m_1m_2}

D=A+k_1m_1

D+k_4m_1m_2=C+k_3m_3\\ D+k_4m_1m_2\equiv C \pmod{m_3}\\ k_4\equiv \frac{C-D}{m_1m_2} \pmod{m_3}

求出k_4那么x\equiv D+k_4m_1m_2 \pmod{m_1m_2m_3},

因为x<m_1m_2m_3,所以x=D+k_4m_1m_2

拆系数FFT(MTT)

直接FFT精度不足,我们可以采用拆系数FFT

把每个数拆成ak + b的形式

然后再相乘、合并即可

即假设给定多项式N,MN(x)=ka(x)+b(x),M(x)=kc(x)+d(x)

\begin{aligned} &\quad N(x)M(x)\\ &=(ka(x)+b(x))(kc(x)+d(x))\\ &=k^2a(x)c(x)+k(a(x)d(x)+b(x)c(x))+b(x)d(x) \end{aligned}

8次DFT

优化版需4次DFT

一下a,b,c,d为上述a(x),b(x),c(x),d(x)

A_j=a_j+ib_j,B_j=c_j+id_j

\begin{aligned} &\quad A(w_n^j)_x\\ &=(a_x+ib_x){w_n^j}^x\\ &=a_x(\cos \frac{2\pi xj}n+i\sin \frac{2\pi xj}{n})+b_x(i\cos \frac{2\pi xj}n - \sin \frac{2\pi xj}n) \end{aligned}

同理

\begin{aligned} &\quad A(w_n^{-j})_x\\ &=(a_x+ib_x){w_n^{-j}}^x\\ &=a_x(\cos \frac{2\pi xj}n-i\sin \frac{2\pi xj}{n})+b_x(i\cos \frac{2\pi xj}n + \sin \frac{2\pi xj}n) \end{aligned}

因此

a(w_n^j)_x=\frac {A(w_n^j)_x.real+A(w_n^{-j})_x.real}2+i\frac{A(w_n^j)_x.imagine-A(w_n^{-j})_x.imagine}2

(实部为real,虚部为imagine)

同理

b(w_n^j)_x=\frac {A(w_n^j)_x.imagine+A(w_n^{-j})_x.imagine}2+i\frac{A(w_n^j)_x.real-A(w_n^{-j})_x.real}2

C(x)=a(x)*B(x)=a(x)*c(x)+i*a(x)*d(x)\\ D(x)=b(x)*B(x)=b(x)*c(x)+i*b(x)*d(x)

可以发现C的实部为a(x)c(x),虚部为a(x)d(x),

同理D的实部为b(x)c(x),虚部为b(x)d(x),

那么只需要4次FFT就可以求出a(x)c(x),a(x)d(x),b(x)c(x),b(x)d(x)

实测FFT常数大,还是跑不过NTT

多项式乘法逆

给出多项式A(x),求B(x)使A\cdot B \equiv 1 \pmod{x^n}

假设已经求出B'满足A\cdot B' \equiv 1 \pmod{x^\frac n2}

\because A\cdot B \equiv 1 \pmod {x^n}\\ \because A\cdot B' \equiv 1 \pmod{x^\frac n2}\\ \therefore A \cdot (B-B') \equiv 0 \pmod{x^\frac n2}\\ \therefore B-B' \equiv 0 \pmod{x^\frac n2}\\ \quad (B-B')^2 \equiv 0 \pmod{x^n}\\ \quad B^2-2BB'+B'^2 \equiv 0 \pmod{x^n}\\ \therefore A(B^2-2BB'+B'^2) \equiv 0 \pmod{x^n}\\ \quad AB^2-2ABB'+AB'^2 \equiv 0 \pmod{x^n}\\ \because A\cdot B \equiv 1 \pmod {x^n}\\ \therefore B-2B'+AB'^2\equiv 0 \pmod{x^n}\\ \quad B\equiv 2B'-AB'^2 \pmod{x^n}

多项式除法与取模

给出多项式n次多项式F(x)m次多项式G(x),求出多项式Q(x),R(x)满足以下条件:

  • Q(x)次数为n-m,R(x)次数小于m
  • F(x)=Q(x)*G(x)+R(x)

F_r(x)=x^nf(\frac 1x),

可以发现A_r[i]=A[n-i](A_i=[x^i]F(x),也就是F(x)的第n项的系数)

F(x)=Q(x)*G(x)+R(x)\\ F(\frac 1x)=Q(\frac 1x)*G(\frac 1x)+R(\frac 1x)\\ x^nF(\frac 1x)=x^{n-m}Q(\frac 1x)\cdot x^mR(\frac 1x)+x^{n-m+1} \cdot x^{m-1} R(\frac 1x)\\ F_r(x)=Q_r(x)*R_r(x)+x^{n-m+1}\cdot R_r(x)\\~\\ F_r(x)\equiv Q_r(x)*G_r(x) \pmod{x^{n-m+1}}\\ Q_r(x)\equiv F_r(x)*G_r(x)^{-1} \pmod{x^{n-m+1}}\\ R(x)=F(x)-G(x)*Q(x)

多项式开根

给定多项式A(x),求出B(x)使B(x)^2\equiv A(x) \pmod{x^n}

B'(x)^2\equiv A(x) \pmod{x^{\frac n2}}

\displaystyle B(x)\equiv B'(x) \pmod{x^{\frac n2}}\\ B(x)-B'(x)\equiv 0 \pmod{x^{\frac n2}}\\ (B(x)-B'(x))^2\equiv 0 \pmod{x^{\frac n2}}\\ B^2(x)+B'^2(x)-2B(x)B'(x)\equiv 0 \pmod{x^n}\\ A(x)+B'^2(x)-2B(x)B'(x)\equiv 0 \pmod{x^n}\\ B(x)=\frac{A(x)+B'^2(x)}{2B'(x)}\\

多项式对数函数

前置知识: 求导&积分

求导公式: (x^n)'=nx^{n-1}

积分公式: \int x^n dx=\frac 1{n+1}x^{n+1}

求导与积分互逆

\ln' x=\frac 1x

给出多项式A(x),求出B(x)使B(x)\equiv \ln A(x)

对两边分别求导

\begin{aligned} B'(x) &=\ln' A(x)\\ &=ln'(A(x)) A'(x)\\ &=\frac{A'(x)}{A(x)} \end{aligned}

将读入A求导得到a,求逆得到b,B'=a*b

G'求积分就可以得到G

多项式指数函数

前置知识: 泰勒展开&牛顿迭代

牛顿迭代:

证明: http://blog.miskcoo.com/2015/06/polynomial-with-newton-method

对于一个函数G(x),求满足条件G(F(x)) \equiv 0 \pmod {x^n}的多项式F(z)

\displaystyle F(x)\equiv F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n}

这里F_0(x)指的是在模x^{\frac n2}意义下的答案

给出多项式A(x),求出B(x)使B(x)\equiv e^{A(x)}

变形得\ln B(x) -A(x)=0

G(B(x))=\ln B(x) - A(x),现在要求G的零点

G'(B(x))=\frac 1{B(x)}

代入牛顿迭代公式得

B(x)\equiv B_0(x)(1-\ln B_0(x)+A(x)) \pmod{x^n}

多项式快速幂

给定多项式A(x),求出B(x)使B(x)\equiv A^k(x) \pmod{x^n}

取对数

\ln B(x)\equiv kA(x) \pmod{x^n}

再取指数

B(x)=e^{kA(x)}

https://www.cnblogs.com/xzyxzy/p/9270361.html

多项式全家桶
comment评论
Search
search