我的代码模板依赖于我自定义的预处理器,它通过 DFS 把所有引入的模板展开。

我的模板风格是简单封装:在保持易用的同时,封装尽量的薄。

Data Struct

基础数据结构。

Math

基础数学算法。

Basic

我也不知道这东西该放哪,就放到这里吧。

  • modint:m32

NTT-int

简化多项式板子,码量少,常数较大。

  • fps/O.hpp:多项式基础结构,用牛顿迭代完成操作。
  • fps/F.hpp:与上面的相同,略卡常数。
  • cdq.hpp:非递归 CDQ 分治。
  • eval.hpp:多点插值,多点求值。

没有用的 NTT-mint

基于 modint 的多项式板子,注重易用性和常数,码量较大。

每一种算法可能有多种实现。

多项式类的定义

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

半在线卷积(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

积分、求导、多点求值、多点插值、快速幂。