由于某种难以言说的原因 简而言之就是我比较懒得打 \(\LaTeX\) 所以进行一下多项式浅浅浅谈
郑重声明：本文就是在闲扯 不能作为正确的多项式研究资料
我推荐算法导论 同济出版社的高等数学(掌握一定的高数基础)和oi-wiki 和马蜂看得过去的洛谷板子用来贺
更好的多项式乘法
(默认知道啥叫卷积)
首先我们发现 \(\sum_{i=0}^{n-1} a_ix^i\) 这种系数表达式是有局限的 它在乘法时必须 \(n^2\) 配对 所以我们不用系数表达式了 我不做人了 JoJo
点值表示法
我们惊喜的发现点值表示下多项式相乘是 \(O(n)\) 的 如果我们采用点值表示法进行多项式乘法 那么复杂度瓶颈就在点值和系数转化上
我们发现拉格朗日插值取等距点可以 \(O(n)\) 插值 但是没有任何用 因为转点值是 \(O(n^2)\) 的
复数
代数基本定理一句话题意： 一个 \(n\) 次方程有 \(n\) 个复数根(重根记多次)
FFT的基础：折半引理
这有个锤子用呢 确实有个锤子用
DFT
设 \(A1(x)=\sum_{i=0}^{(n-1)/2} a_{2i}x^{2i}\)
\(A2(x)=\sum_{i=1}^{(n-1)/2} a_{2i-1}x^{2i-1}\)
则 \(A(x)=\sum_{i=0}^{n-1} a_ix^i=A1(x^2)+xA2(x^2)\)
设我们求 \(n\) 个点处值 选取 \(n\) 个点为方程 \(x^n=1\) 的 \(n\) 个根
即 \(\omega_n^0\) , \(\omega_n^1\) , \(\omega_n^2\) \(…\) \(\omega_n^{n-1}\)
我们要求每一个根的 \(A(x)\)
发现前半段和后半段的平方是一样的
所以 \(A(x)\) 我们只用算一半就好因为剩下一半计算的过程是一样的 然后继续递归处理
复杂度就是 \(O(n\log n)\)
上述过程叫 \(DFT\)
看到这你可能会莫名其妙 因为我没好好写
我的建议是去看算法导论 个人感觉是最好理解的
那系数转点值搞完了 下一步是插值
如果我们把求值和插值都写成矩阵乘法形式 我们就会发现 两个矩阵系数正好相反
所以我们直接套 \({\!-\!\!-\!\!-\!\!-\!\!}\llap{DFT}\) 函数就好了
上述过程叫 \(IDFT\)
即 \(DFT\) 的逆变换
严谨证明还得看拉格朗日插值
递归版常数巨大 用蝴蝶操作之类变成非递归版就快了
此外 在 \(FFT\) 中我们强制 \(n\) 为 \(2\) 的次幂 不足的为 \(0\) 这样就不用特判了……
NTT
发现我们的优化是基于折半引理的
所以只要能达到类似\({(\omega_n^{\small n/2+k})}^2={\left(\omega_n^{\small k}\right)}^2\)的效果就可同理优化
原根
去看oi-wiki
实际上只要记住998244353和1003545809的原根是3
然后直接把复数换成原根即可
注意事项
1 每次清空数组是清空 \(N\) 而不是清空 \(n\)
2 优化高精度除非最后再处理一遍 否则不能多数相乘一遍 \(IDFT\) 也不能压位 原因是不满足卷积性质 但可以通过后续处理解决
其他应用
1 背包
2 有一些反转之后就成为了卷积
3 重中之重 字符串匹配：
如果两个字符匹配 即两字符平方差为 \(0\) 字符串也满足 （单纯作差只能满足单个字符匹配）
反过来展开即构成卷积
存在通配符时：
匹配函数再乘上一方或两方的字符 （通配符对应数值为 \(0\) ）
多项式半家桶
多项式求逆 开跟 求 \(\ln\) 求 \(\exp\)
不学牛顿迭代也可以 但是会越来越怪
高中数学书上的牛顿迭代：精确根
多项式牛顿迭代：呵呵
需要掌握基本导数表 泰勒展开 和一定的偏导数知识
(前面俩在高等数学上 后一个在高等数学下)
具体都可以看oi-wiki
里面是非牛顿迭代做法 但牛顿迭代里有牛顿迭代版做法
大底思路是构造一个同余 \(0\) 的多项式然后倍增牛顿迭代
多项式开跟理论上要二次剩余 但是各个平台上都强制 \(a_0=1\)
垃圾版的二次剩余直接模拟 \(BSGS\) 就好
生成函数
掌握二项式定理 和其它一系列反演知识 还有多项式科技 （至少半家桶）
你以为我会？博客完结
原文地址：http://www.cnblogs.com/Sakura-Lu/p/16818926.html
