对于一个函数 \(F(n)\)，要在较低时间内求前缀和 \(S_F(n)=\sum_{i=1}^nF(i)\)。
假设我们能找到一个函数 \(G(n)\) 使得 \(G(n),S_{F \oplus G}(n)\) 能在较短时间内算出。
其中 \(\oplus\) 表示狄利克雷卷积，\((F\oplus G)(n)=\sum_{d|n}F(d)G(\frac{n}{d})\)
那么就有
\[ \begin{aligned} \displaystyle S_{F\oplus G}(n)&=\sum_1^n G(i)S_F(\lfloor\frac{n}{i}\rfloor) \\ \displaystyle G(1)F(n)&=S_{F\oplus G}(n)-\sum_2^nG(i)S_F(\lfloor\frac{n}{i}\rfloor) \end{aligned} \]
这个 \(\lfloor\frac{n}{i}\rfloor\) 的个数是 \(O(\sqrt n)\) 的，数论分段求解。
\(I_n\) 是 \(n\) 阶单位矩阵，即主对角线是 \(1\) 的 \(n\) 阶矩阵
一个矩阵 \(A\) 的 \(|A|\) 是 \(A\) 的行列式。
默认 \(A\) 是一个 \(n\times n\) 的矩阵。
对于一个矩阵 \(A\)，它的一个零化多项式 \(f(\lambda)\) 是满足 \(f(A)=0\) 的多项式，定义域包含矩阵。
对于一个 \(n\) 行 \(n\) 列的矩阵 \(A\)，有矩阵的行列式（常用 \(\det(A),|A|\) ）表示。
如果将矩阵的每一行视为一个 \(n\) 维向量，则 \(n\) 阶行列式的意义可以看做是有向长度/面积/体积在 \(n\) 为空间下的扩展。
具体的例子：
\(n=1\) 时，\(|A|=A_{1,1}\)，即有向长度。
\(n=2\) 时，\(|A|=A_{1,1}A_{2,2}-A_{1,2}A_{2,1}=\vec{A_1}\times \vec{A_2}\)。
因此也可以得到常用的一个 3维向量外积的表达式
\[ \vec{a}\times \vec{b}=\begin{vmatrix} \vec{x}\ \ \vec{y}\ \ \vec{z} \\ a_1\ a_2\ a_3\\ b_1\ b_2\ b_3\end{vmatrix} \] 其中 \(\vec{x},\vec{y},\vec{z}\) 是三维平面的三个维度的单位向量。
上式即将有向体积中的一个向量改为单位向量后压缩到一个平面上。
\[ \ \]
枚举 \(1,2,\cdots,n\) 的一个排列 \(p_i\)，设排列 \(p\) 的逆序对为 \(f(p)\)。
则 \(\displaystyle |A|=\sum (-1)^{f(p)} \Pi A_{i,p_i}\)，其中 \((-1)^{f(p)}\) 也记作 \(\sigma(p),\text{sgn}(p)\)。
\[ \ \]
1.交换任意两行（列）得到矩阵 \(A'\)，则 \(|A'|=-|A|\) （交换后每个排列 \(f(p)\) 的奇偶性改变）。
2.对于某一行（列）乘上一个值 \(k\) 得到矩阵 \(A'\)，则 \(|A'|=k|A|\)。
3.某一行减去另一行的 \(k\) 倍得到矩阵 \(A'\)，则 \(|A'|=|A|\)。
根据性质1,2,3 可以对于矩阵进行高斯消元。
而对于一个上三角/下三角矩阵，带入上面的基本求法，显然能够得到 非 0 值 的排列只有对角线 \(p_i=i\)。
因此得到上/下三角矩阵之后就可以快速求解，复杂度为高斯消元的 \(O(n^3)\)。
1.1分块，莫队(奇偶排序加速莫队)
1.2树状数组
1.3线段树，函数式线段树，可持久化函数式线段树(主席树)，\(\text{Segmentbeats}\)(吉老师树) , \(\text{ZKW}\)线段树，线段树合并
1.4二叉堆，左偏树，配对堆，可持久化左偏树
1.5平衡树：\(\text{Splay}\)，\(\text{Treap}\)，非旋\(\text{Treap}\)，可以持久化非旋\(\text{Treap}\)
1.6李超树
17.线段树分治，半动态线段树分治（一边分治一边得到加边的范围）
1.7\(\text{K-D Tree}\)
1.8树套树，\(\text{CDQ}\)分治，高维问题
1.9莫队二次离线
(latest updated on 2021.02.23)
前置知识 \(\text{NTT}\) 。
所有操作均在对 \(P=\text{998244353}\) 取模下进行。
（代码在最下面）。
下文中 \(\pmod {x^n}\) 表示求出了多项式的前 \(n\) 项。
\([x^i]F(x)\) 表示 \(F(x)\) 第 \(i\) 项的系数。
每个小问题的模板题都可以在洛谷上找到。
对于给定的元 \(a,b,c,n\)：
设 \(f(i)=\lfloor\frac{ai+b}{c}\rfloor\)。
求：
参考文献：2019集训队论文，钟子谦《两类递推数列的性质和应用》
这篇文章介绍如何求解，线性递推的应用更多在这里
数列 \(\{a_0,a_1,\cdots \}\)，
向量序列 \(\{v_0,v_1,\cdots\}\)，
矩阵序列 \(\{M_0,M_1,\cdots\}\)。
的线性递推
序列 \(a_0,a_1,\cdots,a_n\) 的线性递推的定义为：
对于一个常数列 \(r_0,r_1,\cdots,r_m(r_0=1)\)
记 \(\lambda(i,r)=\sum_{j=1}^{m}a_{i-j}r_j\)
\(\Delta(i,r)=\sum_{j=0}^m a_{i-j}\)
则满足 \(\forall i\ge m,\Delta(i,r)=0\) 的序列为一个线性递推序列。
稍作变换可以得到更加符合常理的形式：\(a_i=\sum_{j=1}^m r'_j \cdot a_{i-j}\)。
正常 \(\text{DFT/IDFT}\) 是构造一个特殊的点值式，即 \(x_i=\omega_{n}^i\)。
如果能通过题目条件构造出来这样的点值，就可以直接 \(\text{DFT/IDFT}\)。
那如果不能的话。。。。。
\[ \begin{aligned} &\det\left(\begin{array}{cccc} x_0^0 & x_1^0 & \cdots & x_{n-1}^0\\ x_0^1 & x_1^1 & \cdots & x_{n-1}^1\\ \vdots & \vdots & \vdots &\vdots\\ x_0^{n-1} & x_1^{n-1} & \cdots & x_{n-1}^{n-1} \end{array}\right) \\ \\ & 第\ i\ 行减去第\ i-1\ 行乘\ x_0\ ，得到 \\ \\ =&\det\left(\begin{array}{cccc} 1 & 1 & 1 & \cdots & 1\\ 0 & x_1^0(x_1-x_0) & x_2^0(x_2-x_0) & \cdots & x_{n-1}^0(x_{n-1}-x_0)\\ 0 & x_1^1(x_1-x_0) & x_2^1(x_2-x_0) & \cdots & x_{n-1}^1(x_{n-1}-x_0)\\ \vdots & \vdots & \vdots &\vdots & \vdots \\ 0 & x_1^{n-2}(x_1-x_0) & x_2^{n-2}(x_1-x_0) & \cdots & x_{n-1}^{n-2}(x_{n-1}-x_0) \end{array}\right) \\ \\ & 于是可以把第一行第一列去掉，然后剩下的每一列提取 x_i-x_0，得到 \\ \\ =&\prod_{i>1} (x_i-x_0) \left(\begin{array}{cccc} x_1^0 & x_2^0 & \cdots & x_{n-2}^0\\ x_1^1 & x_2^1 & \cdots & x_{n-2}^1\\ \vdots & \vdots & \vdots &\vdots\\ x_0^{n-2} & x_1^{n-2} & \cdots & x_{n-2}^{n-2} \end{array}\right) \\ \\ & 简单归纳知道答案就是 \\ =&\prod_i\prod_j (x_i-x_j) \end{aligned} \]
组合数 \(\displaystyle C(n,m)=C_n^m=\binom{n}{m}\).
\(C(n,m)=C(n-1,m-1)+C(n-1,m)\).
\(\displaystyle \sum_{i=0}^n C(n,i) =2^n\).
\(\displaystyle \sum_0^n (-1)^i C(n,i)=[n=0]\).