数学相关
常系数线性齐次递推矩阵的特征多项式
常系数线性齐次递推中，若有
\[ f(n)=\sum_{j=1}^ka_jf(n-j) \] 则有\(k\)阶转移矩阵\(M\)如下：\[ M=\begin{bmatrix} 0&0&0&...&a_k\\ 1&0&0&...&a_{k-1}\\ 0&1&0&...&a_{k-2}\\ 0&0&1&...&a_{k-3}\\ ...&...&...&...&...\\ 0 &0&...&1&a_1 \end{bmatrix} \] 其中\(M_{i,j-1}=1\)（\(2\leq i\leq k\)），\(M_{i,k}=a_{k-i+1}\)（\(1\leq i\leq k\)）其特征多项式\(f(\lambda)\)为：
\[ f(\lambda)=det(\lambda I-M)=\begin{bmatrix} \lambda&0&0&0&-a_k\\ -1&\lambda&0&0&-a_{k-1}\\ 0&-1&\lambda&0&-a_{k-2}\\ ...&...&...&...&...\\ 0&0&...&-1&\lambda-a_1 \end{bmatrix} \] 其中\(f(\lambda)_{i,j-1}=-1\)（\(2\leq i\leq k\)），\(f(\lambda)_{i,i}=\lambda\)（\(1\leq i< k\)）\(f(\lambda)_{k,k}=\lambda-a_1\)，\(f(\lambda)_{i,k}=-a_{k-i+1}\)（\(1\leq i < k\)）
对\(f(\lambda)\)拉普拉斯展开化简得到
\[ f(\lambda)=\lambda^k-\sum_{i=1}^ka_i\lambda^{k-i} \]
二项式相关
二项式反演
对于两个函数\(f\)和\(g\)，
\[ f(n)=\sum_{j=0}^n{n \choose j}g(j)\quad \Leftrightarrow\quad g(n)=\sum_{j=0}^n(-1)^{n-j}{n\choose j}f(j) \]上指标反转
\[ {n \choose m}=(-1)^m{m-n-1\choose m} \]
组合数卷积求和
给定\(n\)，\(a\)，\(b\).
\[ \sum_{i=0}^n{n\choose a}{n-i \choose b}={n+1\choose a+b+1} \] 组合意义解释：\({n+1 \choose a+b+1}\)相当于先枚举第\(a+1\)个球的位置\(p\)，然后再计算从\([1,p)\)中选\(a\)个球、从\((p,n+1]\)中选\(b\)个球的方案数。枚举\(p\)对应着枚举原式中的\(i\)如何分割\(n\)，而\([1,p)\)选\(a\)和\((p,n+1]\)选\(b\)分别对应了原式的两个组合数。Lucas定理
\[ {ap+c \choose bp+d}\equiv{a\choose b}{c\choose d} \pmod{p} \]
递归计算，时间复杂度为\(O(plog_pn)\)
莫比乌斯反演
\[ f(n)=\sum_{d|n}g(d) \quad \Leftrightarrow \quad g(n)=\sum_{d|n}\mu(\frac n d)f(d)\\ f(n)=\sum_{n|d}g(d) \quad \Leftrightarrow \quad g(n)=\sum_{n|d}\mu(\frac d n )f(d) \]
斯特林数
第二类斯特林数通项公式
\[ \begin{aligned} \begin{Bmatrix}n\\m\end{Bmatrix}&=\frac 1 {m!}\sum_{j=0}^m(-1)^j {m\choose j}(m-j)^n\\ &=\sum_{j=0}^m \frac{(-1)^j}{j!(m-j)!}(m-j)^n \end{aligned} \]
自然数幂的斯特林数展开
\[ i^k=\sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} {i \choose j}j! \]
自然数幂求和
\[ \begin{aligned} Sum_k(n)&=\sum_{i=1}^ni^k\\ &=\sum_{j=1}^k\begin{Bmatrix}k\\j\end{Bmatrix}\frac{ {(n+1)}^\underline{j+1}}{j+1} \end{aligned} \]