我的代码模板依赖于我自定义的预处理器,它通过 DFS 把所有引入的模板展开。
- index.hpp:公共文件头。
我的模板风格是简单封装:在保持易用的同时,封装尽量的薄。
Data Struct
基础数据结构。
- fwtree/1.hpp:普通树状数组。
- fwtree/2.hpp:支持区间修改、区间查询的树状数组。
- SegmentTree/1.hpp:普通线段树示例,不可引入。
- SegmentTree/2.hpp:带懒标记的线段树示例,不可引入。
Math
基础数学算法。
- qpow.hpp:快速幂。
- qpow128.hpp:64 位类型的快速幂。
Basic
我也不知道这东西该放哪,就放到这里吧。
- modint:m32。
NTT-int
简化多项式板子,码量少,常数较大。
没有用的 NTT-mint
基于 modint 的多项式板子,注重易用性和常数,码量较大。
每一种算法可能有多种实现。
多项式类的定义
- poly/1.hpp:继承于
vector<m32>。
NTT
多项式逆
- inv/1.hpp:12E 的牛顿迭代 inv,和 16E 的牛顿迭代 div。
- inv/2.hpp:10E 的牛顿迭代 inv,和 13E 的牛顿迭代 div。
- inv/3.hpp:24E 的牛顿迭代 inv,和 28E 的牛顿迭代 div。
- inv/6.hpp:半在线卷积实现的 inv & div。
- inv/7.hpp:全在线卷积实现的 inv & div。(没啥用)
- inv/8.hpp:10E 的分块牛顿迭代 inv,和 10E 的分块牛顿迭代 div。
多项式 exp
- exp/1.hpp:20E 的牛顿迭代 exp。
- exp/2.hpp:17E 的牛顿迭代 exp。
- exp/3.hpp:32E 的牛顿迭代 exp。
- exp/5.hpp:半在线卷积实现的 exp。
- exp/6.hpp:全在线卷积实现的 exp。(没啥用)
- exp/7.hpp:14E 的分块牛顿迭代 exp。
半在线卷积(CDQ 分治)
- cdq/3.hpp:2 叉的半在线卷积实现,不保存卷积结果。
- cdq/4.hpp:B 叉的半在线卷积实现,不保存卷积结果。
- cdq/5.hpp:2 叉的半在线卷积实现,保存卷积结果。
- cdq/6.hpp:B 叉的半在线卷积实现,保存卷积结果。
- cdq/7.hpp:略微卡常的 B 叉在线卷积实现。
全在线卷积
- oc/1.hpp:全在线卷积的实现。(感觉挺快的
多项式 sqrt
- sqrt/1.hpp:11E 的牛顿迭代 sqrt。
- sqrt/5.hpp:全在线卷积实现的 sqrt。
- sqrt/8.hpp:8E 的分块牛顿迭代 sqrt。
积分、求导、多点求值、多点插值、快速幂。