QMath

QMath 是一个万能的数学库，它打包了和数论、线性代数、多项式函数、平面几何……相关的模板。可以方便的实现求导、插值、向量运算、快速傅里叶变换（FFT）、高斯消元……

---

LinearAlgebra

简介

这一文件主要集成线性代数相关内容，目前有：矩阵。

Matrix

简介

自 2025.07.16 起 Matrix 从 vector 版本更新为指针版本。该版本加减乘、标量操作、转置等都已用指针加法尽量消除了寻址乘法，已是极致 cache-friendly 写法，构造、赋值、拷贝均用 std::copy 或 fill_n，operator*、operator*= 都已用局部变量缓存，避免重复解引用，没有多余的临时对象或不必要的拷贝。没有多余的虚函数或 RTTI，没有多余的内存分配。该版本 Matrix 单核性能已几乎优化到极致，难以有更大突破，相比于 vector 版本在矩阵大小中等的情况下速度提升了 $5\sim10$ 倍。更多算法、多线程相关的优化敬请期待。

该版本未添加错误处理相关功能，请确保使用正确。

位置

该类型位于 LinearAlgebra 文件的 LinearAlgebra 命名空间中。

使用方法

1. 构造函数

   使用如下方法会构造出一个高为 $n$，宽为 $m$，初始值为全 $x$ 的矩阵，矩阵中存储类型为 Type 的值。若不填 $x$ 则会使用 Type(0) 初始化矩阵中的数，请确保 Type(0) 是合法的，否则你需要手动修改构造函数源代码才能使用。

   Matrix<Type> a(n, m, x);

   你可以同时指定 $n,m$，也可以同时将 $n,m$ 留空（同时留空会构造一个空矩阵）。但不能只指定 $n,m$ 其中一个。

   你还可以传入一个二维 vector 来构造矩阵。

   Matrix<Type> a(vector<vector<Type>>(...));

2. 运算符重载

   • =：可以将一个矩阵赋给另一个矩阵，也可以将一个二维 vector 赋给矩阵。
   • +：矩阵 $+$ 矩阵、矩阵 $+$ 数字（给矩阵中的每一个数都加上“数字”），没有重载数字 $+$ 矩阵。
   • -：和 + 类似，同样重载了矩阵 $-$ 数字。
   • +=：矩阵 += 矩阵、矩阵 += 数字。
   • -=：和 += 类似。
   • *：矩阵 $\times$ 矩阵、矩阵 $\times$ 数字（给矩阵中的每一个数都乘上“数字”），没有重载数字 $\times$ 矩阵。
   • *=：矩阵 *= 矩阵，矩阵 *= 数字。
   • %：矩阵 % 矩阵，将两个大小形状相同的矩阵中的每个数对应相乘，然后放在结果矩阵的相应位置上。
   • %=：% 运算的 %= 版本。
   • ==、!=：判断两个矩阵大小、形状、内容是否完全相同。
   • (size_t row, size_t col)：返回矩阵第 $row$ 行第 $col$ 列的值（带引用）。
   • []：若传入 $i$ 则返回矩阵第 $i$ 行的起始指针。
   • [][]：若传入 $i,j$ 则返回矩阵第 $i$ 行第 $j$ 列的值（带引用）。

3. 一些方法

   • size_t N()：返回矩阵的行数。
   • size_t M()：返回矩阵的列数。
   • Matrix transpose()：返回该矩阵转置后的矩阵。
   • Matrix& transposeSelf()：将自己转置，然后返回自己的引用。
   • Matrix applyFunction(Type (*func)(Type) 或 Type (*func)(const Type&))：创建一个大小形状相同的结果矩阵，结果矩阵中每个数 $x$ 和其在原矩阵中位置对应的数 $y$ 的关系为：$x=func(y)$，然后返回结果矩阵。
   • Matrix& applyFunctionSelf(Type (*func)(Type) 或 Type (*func)(const Type&))：令该矩阵中的每一个数 $x$ 变为 $func(x)$，然后返回自己的引用。
   • Matrix& resize(size_t n, size_t m, Type x = Type(0))：先将该矩阵清空，再构造一个大小为 $n\times m$，初始值为 $x$ 的矩阵作为该矩阵，然后返回自己的引用。

---

Function

简介

这一文件主要集成函数相关内容，目前有：多项式函数、一次函数、二次函数。

由于二次函数相关内容涉及平面坐标点，所以这一文件依赖于文件 Geometry，使用时请确保它们在同级文件夹或手动将相关依赖 include 进去。

Polynomial

简介

顾名思义，这是一个和多项式函数有关的类，它使用 vector 作基类，vector 可用的功能，它基本都可用，其中集成了快速傅里叶变换（FFT）、快速沃尔什变换（FWT）——与卷积、或卷积、异或卷积。

一个多项式函数形如：

$$f(x) = a_0x^0 + a_1x^1+a_2x^2\cdots a_nx^n=\sum\limits_{i=0}^n{a_ix^i}$$

位置

该类型位于 Function 文件的 Function 命名空间中。

使用方法

1. 构造函数

   使用如下方法会构造出一个项数为 $n$，次数为 $n-1$，系数类型为 Type，每一项系数初始值都为 $x$ 的多项式函数。其中 $n,x$ 默认为 $0$（你需要确保 Type(0) 是合法的，否则你需要手动修改源代码）。

   Polynomial<Type, TypeFFT, std::round, std::sin, std::cos> a(n, x, 3.14159265358979);

   可以看到，在构造的过程中传入了 TypeFFT、std::round、std::sin、std::cos。它们的具体定义是这样的：

   template<typename T = double, typename TFFT = double,
       T (*Round)(TFFT) = std::round,
       TFFT (*Sin)(TFFT) = std::sin,
       TFFT (*Cos)(TFFT) = std::cos>

   传入它们是在为快速傅里叶变换（FFT）作准备，在非 FFT 相关运算时会采用 Type 类型，在 FFT 相关运算时会将 Type 强转为 TFFT 类型，请确保定义了 Type 强转 TFFT 的函数，在 FFT 相关运算结束时，会使用 Round 函数将 TFFT 类型转回 Type 类型（Round 可能是四舍五入函数）。与此同时，请传入与 TFFT 类型相对应的正弦和余弦函数，如果你不需要使用快速傅里叶变换（FFT），可以随意设置 TFFT 并传入三个合法空函数。与此同时，还向构造函数传入了值 3.14159265358979，这是 $\pi$ 的近似值，依然服务于快速傅里叶变换（FFT），如果你不传入 $\pi$ 的近似值，则它默认为 std::acos(-1)，请保证传入的 $\pi$ 的近似值和 TFFT 类型相符。

2. 运算符重载

   • =：拷贝多项式。
   • +、+=：多项式相加。
   • -、-=：多项式相减。
   • *、*=：多项式相乘（加法卷积，使用蝶形变换 + 快速傅里叶变换（FFT）实现，时间复杂度 $O(n\log{n})$）。
     对于以上运算，该类型会自动调整多项式的次数。
   • |、|=：多项式的或卷积。
   • &、&=：多项式的与卷积。
   • ^、^=：多项式的异或卷积。
     对于以上运算，均使用快速沃尔什变换（FWT）实现，时间复杂度均为 $O(n\log{n})$。若多项式 $a$ 与 $b$ 进行以上几种运算的任意一种，记 $a$ 的项数为 $sz(a)$， $b$ 的项数为 $sz(b)$ 则结果多项式的项数为：最小的大于等于 $\max\{sz(a),sz(b)\}$ 的 $2$ 的整次幂。
   • []：若传入 $i$，则返回多项式 $i$ 次项的系数（带引用）。

3. 一些方法

   • T derivative(const T& _x)：用于计算多项式在 $x=\_x$ 处的导数。
   • T calc(const T& _x)：用于计算多项式在 $x=\_x$ 处的函数值。
     以下从 vector 继承而来的方法不再指明输入值和返回值类型（主要我也不太确定每一个具体是什么。。。）
   • size()：返回多项式的项数。
   • resize()、begin()、end()、front()、back()、erase()、insert()……：不再一一列举了，用法和 vector 完全一样，甚至不影响其配合 STL 使用，例如：

   sort(p.begin(), p.end());