进阶算法学习笔记

这大概是最后一份用Markdown写的算法笔记，之后的笔记都用iPad写电子笔记了

P5431 【模板】乘法逆元 2（离线线性求逆元科技）

假设我们需要求 $a_1, a_2, \ldots ,a_n$ 的逆元，令 $A = a_1a_2\ldots a_n$，则$a_1^{-1} a_2^{-1} \ldots a_n^{-1} = (a_1a_2\ldots a_n)^{-1} = A^{-1}$，于是我们只需要一次快速幂或者 ExGCD 求出 $A$ 的逆元，维护出 $a$ 的前缀积 Pre 和后缀积 Suf，则 $a_i^{-1} = Pre_{i-1} \cdot A \cdot Suf_{i+1}$，时间复杂度$\mathcal O(n + \log P)$，空间复杂度 $\mathcal O(4n)$

容斥原理

形式化的用法

CF547C Mike and Foam

容斥原理基本应用，容斥每个质因子，Cnt[i]表示含有因子i的数的个数

莫比乌斯反演

莫比乌斯反演定理的证明，讲的挺好的

约数个数和

积性函数

龙哥的问题

生成函数

食物

多项式全家桶

NTT的一个坑点

计算$\ A(x) \cdot B(x) \bmod x^n$,其中$\ A(x), B(x)$ 都是$\ n\ $项（即$\ \bmod x^n\ $意义下）多项式，不能只取$\ n\ $个点值，因为我们在进行点值相乘的时候，我们是用$\ A(x), B(x) \bmod x^n\ $的精确点值相乘，得到的是$\ A(x) \cdot B(x) \bmod x^{2n}\ $的精确点值，而不是$\ A(x) \cdot B(x) \bmod x^{n}\ $的精确点值，所以做逆变换得到的多项式就是错误的

例如上面的例子：
$$
(2+3x)\cdot(5+7x) \equiv 10 + 29x \pmod {x^n} \
(2+3x)\cdot(5+7x) \equiv 10 + 29x + 21x^2\pmod {x^{2n}}
$$
而上面a[0] * b[0] = 5 * 12 = 60，恰是多项式$\ 10 + 29x + 21x^2\ $在1处的点值，而我们希望的点值是29 + 10 = 39，从下图可以看到，如果我手动改下程序算出来的新多项式的点值，就能逆变换得到正确结果：

1 998244347 0 0 
1 998244347 33 0 0 0 0 0 
1 998244347 33 998244169 1020 0 0 0 0 0 0 0 0 0 0 0 
1 998244347 33 998244169 1020

注意：NTT一定要保证实际计算的两个多项式乘积的最高次项系数 < tot

回到那个困惑我大半天的问题为啥要保证G数组是清空的啊，为啥每次做完了G数组要清空，

实际上牛顿迭代法和普通的推导求逆求出的$\ H(x)\equiv F^{-1}(x) \bmod {x^{\frac{n}{2}}}$确实不需要要求$\ H(x)\ $系数大于等于$\ \frac{n}{2}\ $的项为0，例如$\ 1+6x\ $在$\ \bmod x^2\ $下的逆是$\ 1-6x\ $，我们求出了$\ 1+6x\ $在$\ \bmod x\ $逆是1，则$\ H(x) = 1\ $，按照$\ G(x) \equiv H(x)\cdot(2 - H(x)\cdot F(x)) \pmod {x^n}\ $进行计算，可以得到$\ G(x) = 1\cdot (2 - 1\cdot (1 + 6x)) = 1 - 6x\ $，固然正确，但如果$\ H(x) = 1 + 5x\ $，这样计算的结果是$\ G(x) = (1+5x)\cdot (2 - (1+5x)\cdot (1 + 6x)) \equiv 1 - 6x \pmod {x^2}\ $，也是正确的，但在数学上正确却在NTT上不正确，因为实际计算的两个多项式乘积结果的最高次系数>=tot，我们计算出的点值结果也是次数>=tot的多项式的结果，无法逆变换回去了

NTT模数表

NTT模数表（from Fuyuki(uid=109236)）
//（g 是mod(r*2^k+1)的原根）

素数  r  k  g
3   1   1   2
5   1   2   2
17  1   4   3
97  3   5   5
193 3   6   5
257 1   8   3
7681    15  9   17
12289   3   12  11
40961   5   13  3
65537   1   16  3
786433  3   18  10
5767169 11  19  3
7340033 7   20  3
23068673    11  21  3
104857601   25  22  3
167772161   5   25  3
469762049   7   26  3
1004535809  479 21  3
2013265921  15  27  31
2281701377  17  27  3
3221225473  3   30  5
75161927681 35  31  3
77309411329 9   33  7
206158430209    3   36  22
2061584302081   15  37  7
2748779069441   5   39  3
6597069766657   3   41  5
39582418599937  9   42  5
79164837199873  9   43  5
263882790666241 15  44  7
1231453023109121    35  45  3
1337006139375617    19  46  3
3799912185593857    27  47  5
4222124650659841    15  48  19
7881299347898369    7   50  6
31525197391593473   7   52  3
180143985094819841  5   55  6
1945555039024054273 27  56  5
4179340454199820289 29  57  3

分治NTT

利用CDQ分治的思想，对于当前区间[l, r]，每次先递归计算左半区间[l, mid]，再计算[l, mid]对右半区间[mid + 1, r]的贡献，最后递归计算右半区间[mid + 1, r]

这样只会递归$\log n$层，NTT的总长度为$n\log n$，时间复杂度为$\mathcal O(n\log^2 n)$，思想好理解，但具体细节这里梳理一下：

根据上述，左半区间对右半区间位置在$x$的元素贡献为：
$$
\Large w_x = \sum_{i=l}^r f_i g_{x-i}
$$
梳理一下各个变量的范围：
$$
\Large x \in [mid + 1, r], i \in [l, mid] \Rightarrow x - i \in [1, r - l]
$$