FFT&NTT

FFT

DFT

单位根定义

得到

单位根性质

令

得到

每一项系数 对第 个点值表示的贡献是

IDFT

把DFT的过程写成矩阵的形式

尝试得到左边矩阵（记为 ）的逆，精心构造得到：

发现若

所以得到

即

把IDFT的系数取倒数（即直接虚部取相反数）做一遍DFT再除以 即可

---

NTT

对于一个质数 ，其原根 满足 在模 意义下两两不同

所以

这就需要 是 的幂

所以

因为 且 所以 所以

看上去都没什么问题

所以 DFT 等操作的写法和 FFT 基本等价

---

HDU 6067

每次更改一个多项式的一项系数

对于其点值表示的影响可以顺次算出来

再算一个所有多项式的对应的 个点值表示，改了一个就先除去再修改再乘上即可

因为可能有 不能直接除要记录一下 的个数

最后求 不能每次都还原多项式算和可能常数太大，发现最后求的是一堆多项式的第 项和，直接记录点值和，最后再从这个点值反推回所有的多项式的和对应系数和即可

过了这题才发现一直以来的`NTT``的单位根都处理反了...

一开始以为NTT长度只用到 然而是每个数最多出现 次，NTT长度是

记得去掉第 位的答案，因为不存在只有 位的数字

这题模数小最好预处理逆元到 不然复杂度多个 可能过不了

---

cf286E

每个能表示出来的数一定能被至多两个数表示出来，否则假如只能由 表示，那么就一定不能表示

相当于这个集合对加法封闭

直接对集合里出现的数做集合幂级数再并上一个 即可

考虑每一位：

• 如果原来为 现在不为 那么这个集合不是封闭的输出NO

• 如果原来不为 现在为 不可能因为 次项是

• 如果原来为 现在也为 不影响

• 如果原来不为 现在也不为 那么看它的值是否是 是的话就只能是 和 凑出来，这个数就必选;否则一定有两个非零的和为 ，这个数可以被其他数表示出来所以不必选

---

BZOJ4836 二元运算

在值域上分治，每次直接算两遍左边卷右边的东西贡献到答案数组上

最后每次 出答案

---

cf553E Kyoya and Train

设 表示在时间 时点 到 所需要的最短路的期望

则

令后者为 即第 条边的东西

转移就成了

然后这个 的转移即为

是一个卷积的形式，直接分治 fft 就搞完了

然后记得当把 更新到 时的 数组要开 而不是 因为要把 对 的贡献全部算进去而不是只是 这样

注意边界的最小最大值各取什么，不要想着有clang++查错，一个边界的小问题可能卡半个多小时

---

BZOJ4451 Frightful Formula

这已经可以直接任意模数NTT做了，只是常数大

由于这题的形式特殊，尝试再推一些东西

令

则上面那个东西就是

边界是

后两项是类似的，以 为例

边界

得到

当 时有

同理

然后递推的时候直接 非常优质

---

cf958F

相当于求一堆 的积的某一项

直接分治FTT常数可能有点问题

改成启发式合并，用个堆维护当前最小的多项式的 ，每次合并果子一样合并就行了

---

cf623E

每个数至少使“前缀或”多一位的 ，最多 位所以当 时直接puts("0")

所以现在 同阶了

感觉其他人搞得状态有点麻烦就自己搞了一种（然后发现差不多麻烦）

令 表示前 个数，一共在 个位置下有 的方案数，注意这 个位置是在 中的

最后答案就是

一开始想的转移是

然后发现这个转移太慢了，每次似乎可以转移多个数：

那个 是因为对于右边的 个数的每一个来说，左边 位可以任选 所以是

然后高兴地打了个分治，然后样例就挂了

因为这个 是考虑了 位在 中的位置的，而我们的 相当于已经给这 位确定了位置

所以 还要除以 才是不考虑在 中顺序的方案数

转移即为

然后又调了一年：

• fft精度差要+0.5

• 每次 时精度丢失也很严重