多项式求逆
给定一个多项式 \(F(x)\) ，请求出一个多项式\(G(x)\)， 满足 \(F(x) * G(x) \equiv 1 ( \mathrm{mod\:} x^n )\)。系数对\(998244353\)取模。
考虑边界情况：当\(F(x)\)只有常数项的时候，其逆元显然为常数项的逆元。 我们递归处理这个问题：
现在假设我们已知一个多项式\(G'(x)\),满足： \[F(x)*G'(x)\equiv 1 (\mathrm{mod\:} \ x^{\lceil \frac{n}{2} \rceil})\] 要求的\(G(x)\)满足： \[F(x)* G(x)\equiv 1 (\mathrm{mod\:} \ x^{\lceil \frac{n}{2} \rceil})\] 两式相减得： \[F(x)*[G(x)-G'(x)]\equiv 0(\mathrm{mod\:} \ x^{\lceil \frac{n}{2} \rceil})\] 则可得： \[G(x)-G'(x)\equiv 0(\mathrm{mod\:}\ x^{\lceil \frac{n}{2} \rceil})\] 两边同时平方得： \[G^2(x)-2G(x)*G'(x)+G'^2(x)\equiv 0 (\mathrm{mod\:}\ x^n)\] 上式乘上\(F(x)\): \[G(x)-2G'(x)+F(x)*G'^2(x)\equiv 0 (\mathrm{mod\:}\ x^n)\] 移项得： \[G(x)\equiv 2G'(x)-F(x)*G'^2(x) (\mathrm{mod\:}\ x^n)\] 所以我们可以从下一层的答案推到这一层来。时间复杂度满足递归式: \[T(n)=T(\frac{n}{2})+O(n \log n)\] 解得\(T(n)=O(n \log n)\),与FFT复杂度相同。
## 代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25inline void prework(int limit)
{
for (int i=1;i<limit;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
w[0]=winv[0]=1;w[1]=qpow(g,(p-1)/limit,p);winv[1]=qpow(w[1],p-2,p);
for (int i=2;i<limit;++i)
w[i]=(ll)w[i-1]*w[1]%p,winv[i]=(ll)winv[i-1]*winv[1]%p;
}
void polyinv(int *A,int *B,int deg)
{
static int C[maxn];
if (deg==1) {B[0]=qpow(A[0],p-2,p);return;}
polyinv(A,B,(deg+1)>>1);
int l=0;limit=1;
while (limit<(deg<<1)) limit<<=1,++l;
for (int i=0;i<deg;++i) C[i]=A[i];
for (int i=deg;i<limit;++i) C[i]=0;
prework(limit);
DFT(C);DFT(B);
for (int i=0;i<limit;++i)
B[i]=((ll)B[i]*((2-(ll)C[i]*B[i]%p+p)%p))%p;
IDFT(B);
for (int i=deg;i<limit;++i) B[i]=0;
}
分治FFT
生成函数真的是人类智慧。。。
给定长度为 \(n-1\) 的数组 \(g[1],g[2],..,g[n-1]g[1],g[2],..,g[n−1]\)，求 \(f[0],f[1],..,f[n-1]f[0],f[1],..,f[n−1]\)，其中 \[f[i]=\sum_{j=1}^i f[i-j]g[j]\] 边界为 \(f[0]=1\)。答案模\(998244353\)。
考虑生成函数(不妨设\(g[0]=0\))： \[F(x)=\sum_{i=0}^{\infty} f[i]*x^i\] \[G(x)=\sum_{i=0}^{\infty} g[i]*x^i\] 则我们只要求出来\(F(x)\)这个多项式就可以确定\(f[]\)的值了。
由定义： \[(F*G)=\sum_{i=0}^{\infty}[(\sum_{j=0}^i f[j]*g[i-j])*x^i]\] 分类讨论： 当\(i=0\)时， \[(F*G)(0)=0\] 当i>0时，因为 \[f[i]=\sum_{j=1}^i f[i-j]g[j]\] 所以 \[\sum_{j=0}^i f[j]*g[i-j]=f[i]\] 即得： \[(F*G)(i)=f[i]\] 故， \[F(x)*G(x)=F(x)-f[0]=F(x)-1\] 解得： \[F(x)=\frac{1}{1-G(x)}\] 然后套多项式求逆板子就好了。
代码：（只贴主函数吧）
1 | int main() |
多项式对数函数
给出 \(n-1\) 次多项式 \(A(x)\),求一个 \(\bmod{\:x^n}\)下的多项式 \(B(x)\)，满足 \(B(x) \equiv \ln A(x)\).在 \(\text{mod } 998244353\)mod 998244353 下进行，且 \(a_i \in [0, 998244353) \cap \mathbb{Z}\)
对于一个函数\(F(x)=\sum kx^a\)而言： \[F'(x)=\sum kax^{a-1}\] 同理，对于它的导函数而言， \[\int F'(x)dx=F(x)\] 即对于\(F(x)=\sum kx^a\)， \[\int F(x)dx=(\sum \frac{k}{a+1}x^{a+1})+C\ (C\in \mathbb{R})\] 在下文中，一般把C视为0. 把B'视为关于x的复合函数， \[\because B(x)=\ln A(x)\] \[\therefore B'(x)=A'(x)/A(x)\]
再做一次积分，得： \[B(x)=\int \frac{A'(x)}{A(x)}\] 因为求导和积分我们都可以\(O(n)\)完成，所以总复杂度\(O(n \log n)\).
代码：
1 | inline void polyder(int *A,int *B,int deg) |
多项式指数函数
给出 \(n-1\)次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\)下的多项式 \(B(x)\)，满足 \(B(x) \equiv e^{A(x)}\).
这就比较麻烦。。。 我们考虑两边同时取对数： \[\ln B(x)\equiv A(x) (\bmod\ x^n)\] 移项： \[\ln B(x)-A(x)\equiv 0\ (\mathrm{mod\ } x^n)\] 设\(G(B(x))=\ln B(x)-A(x)\) 则要求的\(B(x)\)就是\(G(B(x))\)的零点。
假设我们已经求得\(B_0(x)\),使得 \[G(B_0(x))\equiv 0 (\bmod \ x^{\lceil \frac{n}{2}\rceil})\] 考虑在\(B_0(x)\)处泰勒展开： \[G(B(x))=\frac{G(B_0(x))}{0!}+\frac{G'(B_0(x))}{1!}(B(x)-B_0(x)) \ (*)\] 为什么后面不再写了呢，是因为: \[\because G(B_0(x))\equiv 0 (\bmod \ x^{\lceil \frac{n}{2}\rceil}),G(B(x))\equiv 0 (\bmod \ x^{\lceil \frac{n}{2}\rceil})\] \[\therefore B_0(x)\equiv B(x)\ (\bmod \ x^{\lceil \frac{n}{2}\rceil})\] 即\(B_0(x)\)和\(B(x)\)在\(x^{\lceil \frac{n}{2}\rceil}\)之前都是相同的。
所以\((B(x)-B_0(x))^2\)最低次的非零项次数也大于\(n\).在膜意义下，后面的项就都为0了qwq。
由\(G(B(x))\equiv 0 \ (\bmod x^n)\),对\((*)\)式整理可得： \[B(x)\equiv B_0(x)-\frac{G(B_0(x)}{G'(B_0(x))}\] 即： \[B(x)\equiv B_0(x)*(1-\ln B_0(x)+A(x)) \ (\bmod x^n)\] 套多项式ln板子即可。
代码：
1 | inline void polyexp(int *A,int *B,int deg) |
MTT（任意模数NTT）
给定 \(2\) 个多项式 \(F(x), G(x)\) ，请求出 \(F(x) * G(x)\)。系数对 \(p\) 取模，且不保证 \(p\) 可以分解成 \(p = a \cdot 2^k + 1\)之形式。 \(1\le n \le 10^5\ ;a_i,b_i\le 10^9;p\le 10^9+9\)
计数题膜数是\(998244353\)当然好，但就是有毒瘤出题人喜欢\(998244853\),\(99824453\)和\(10^9+7\)。。。这样就比较麻烦。所以我们有了任意模数NTT这种操作，它有两种实现形式：三模数NTT和MTT。本文讲解MTT.（\(\text{Matthew99 Theorem Transform}\)) 首先，如果没有精度问题的话，FFT是可以直接做的。但是数太大啦，FFT会爆精度。所以我们把多项式每一个系数拆成A*m+b的形式，m取\(\sqrt P\),一般实现时取\(32768\)，这样A.B就都在int范围之内，乘积就不会超出double的精度范围,把他们分别DFT，计算，再IDFT，就可以认为没有精度误差。就像这样做： \[(am+b)(cm+d)=acm^2+(ad+bc)m+bd\] 这样做八次FFT，合并就可以了
伪\(\cdot\)代码
1 |
|
。。。吗？
八次FFT是不是有点慢呐qwq.. 所以毛爷爷提出了一个优化方案，可以用四次FFT实现这个功能！
前置知识：一次DFT实现将两个多项式在点值和系数表达之间转换（Orz myy
这部分可以去看毛爷爷论文,在2016国家集训队论文集中 加上myy优化的真\(\cdot\)MTT效果拔群，实测比Vectory巨佬的三模NTT快了十倍多....而且还不用解同余方程！但这样对精度要求还是比较高的，所以必须预处理单位复根，或者偷懒用long double.建议预处理一下吧，这样精度高还跑得快
如果实在理解不了，MTT的代码有很强的规律性，所以可以直接背
真\(\cdot\)代码：
1 | inline void DFT(Complex *A,Complex *w,int limit) |