这大概是最后一份用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]
$$
P4245 【模板】任意模数多项式乘法
关于使用 CRT 合并后为何在模 $\text{lcm}$ 下有唯一解,参加rxz的exCRT的题解
本题取 3 个质数 998244353, 1004535809, 469762049
,计算出结果后再使用 CRT 合并,
Burnside 引理和 Polya 定理
串珠子
魔法手链
第一类斯特林数
Prufer 序列
光之大陆
没太懂,那个重复计算是怎么避免的
CDQ 分治
三维偏序
一维排序,二维归并排序,三维树状数组
老C的任务
三维偏序的基本应用,首先将答案写成二维前缀和相减的形式,把询问看作第三维,离线,就变成了三维数点问题
动态逆序对
CDQ分治,下标排序,元素的值归并,时间戳用树状数组。维护时间戳从n ~ 1编号,时间戳越大表示越早被删除
网络流
最小点权覆盖
最大密度子图
不太理解
牛客概率与期望
由于群里没有PPT,就只有截图在这里了
擅长解密的小红
如果一次试验成功的概率是 $p$,那么不断重复直到第一次成功需要的期望次数是 $\dfrac{1}{p}$
Comments | NOTHING