非全面讲解，仅供记录笔记 Dirichlet卷积 \[(f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})\] \[\varepsilon =\mu \ast 1 \iff \varepsilon(n) = \sum_{d\mid n} \mu(d)\] 其中\(\varepsilon\)卷任何函数等于其函数本身。 莫比乌斯函数\(\...

矩阵树定理 定义 邻接矩阵：\(A=(a_{ij})\)，其中 \(a_{ij}\) 表示 \(i\) 到 \(j\) 有几条边相连。 度数矩阵：\(C=(c_{ij})\)，为对角矩阵，其中 \(c_{ii}\) 表示 \(i\) 的度数。 基尔霍夫矩阵：\(D=C-A\)。 余子式：\(M_{ij}\) 表示去掉第 \(i\) 行第 \(j\) 列后得到矩阵的行列式。 ...

“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”——《孙子算经》 中国剩余定理 即求多个同余方程的解。 举个栗子。求一个数x，使得： \[\begin{cases} x≡2\pmod 3\\ x≡3\pmod 5\\ x≡2\pmod {11}\end{cases}\] 设 \(M=3*5*11=165\), \(a1=3\), \(a2=5\),...

二项式反演 \[ \begin{aligned} g_n=\sum_{i=0}^n(-1)^i\binom ni f_i\Leftrightarrow f_n=\sum_{i=0}^n(-1)^i\binom ni g_i\\ g_n=\sum_{i=0}^n\binom ni f_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom...

斐波那契数列 \(F(0)=F(1)=1\) 或 \(F(1)=F(2)=1\)，\(F(i)=F(i-1)+F(i-2)\). 广义斐波那契数列在转移时有系数且首两项给定。 求法 注意到斐波那契数列的转移为一个矩阵乘 \[ \begin{bmatrix}F(i)&F(i-1)\end{bmatrix} \begin{bmatrix} 1&1\\ 1&...

费马小定理 对于任何互质数 \(a,p\),有 \[ a^{p-1}=1\pmod p \] 应用 求逆元： \[ a^{p-2}=a^{-1}\pmod p \]

前言 我原在博客园上发表的这篇文章是阅读排行榜最高的一篇。然而，作为一个刚学竞赛的学生写的东西，它的质量实在堪忧。行列式又是一个及其重要、基础和困难的概念，无论对于大学数学还是高中竞赛。因此，我决定将这篇文章重新编辑，以便更好地帮助学习的人。 如果你想知道行列式是什么，强烈建议先去学习线性代数基础知识，了解什么是向量、矩阵、线性变换以及会用矩阵描述线性方程组，然后认真理解学习行列式的概念...

前言 该内容算法竞赛涉及不多，属于较深概率论内容。 鞅的停时定理 “鞅”，martingale 用来指一类随机过程，定义如下： 鞅是一种离散时间的随机过程 \(X_0,X_1,\cdots\) 满足： \(E(X_t)<\infty,\forall t\geq0\) \(E(X_{t+1}\mid X_0,\cdots X_t)=X_t\) 根据定义可...