数论

Miller-Rabin 素数测试

根据费马小定理，如果一个 \(a\) 不是 \(n\) 的倍数满足 \(a^{n-1}\bmod n-1\ne 1\)，则 \(n\) 一定不是质数。

但是，有的合数对所有这样的 \(a\)，上面式子都不成立，如 \(341\)，称为 Carmichael 数。

另一方面，如果 \(x^2\equiv1\pmod n\) 且 \(x\ne1,x\ne n-1\)，则 \(n\) 也是合数。

Miller–Rabin 算法的流程是：先判断偶数，对于一个奇数，随机选取 \(a\) 进行判定，设 \(n=2^kx\) 且 \(k\) 取最大值，计算 \(a^x,a^{2x},a^{4x}\cdots a^{2^kx}\)，满足两种条件之一说明 \(n\) 是合数：

• \(a^{2^kx}\ne1\)。
• \(a^{2^ix}\ne1,a^{2^ix}\ne n-1,a^{2^{i+1}x}=1\)。

实际运用种，int 范围内选择 \(2,3,61\) 判断，long long 范围内选择前 \(12\) 个素数判断。

Porllad-Rho 分解质因数

先用 Miller-Rabin 判断是否是素数，然后考虑一种暴力思路：随机 \(d\) 若 \(1<\gcd(n,d)<n\) 则找到一个约数，可以递归分解。

这个算法的优化是：随机 \(a_0,d\)，令 \(a_i=a_{i-1}^2+d\bmod n\)，则 \(d=|a_{2k}-a_k|\)。

还可以继续倍增优化：\(d=|a_{2^{\lfloor log_2k\rfloor}}-a_k|\)，同时由于欧几里得算法，\(\gcd(a,n)=\gcd(a\bmod n,n)\)，所以可以多个乘在一起。具体实现可以见代码。

模板

const int checker[] = {2, 3, 5, 8, 11, 13, 17, 19, 23, 29, 31, 37};

inline LL mul(LL a, LL b, LL m)
{
	LL res = a * b - (LL)((long double)a * b / m + 1e-8) * m;
	return res < 0 ? res + m : (res >= m ? res - m : res);
}
inline LL ksm(LL a, LL n, LL P)
{
	LL res = 1;
	while(n)
	{
		if(n & 1) res = mul(res, a, P);
		a = mul(a, a, P);
		n >>= 1;
	}
	return res;
}
inline bool miller_rabin(LL n)
{
	if(n == 1) return 0;
	if(n == 2) return 1;
	if(~n & 1) return 0;
	LL u = n - 1, t = 0;
	while(~u & 1) u >>= 1, t ++ ;
	for(int i = 0; i < 12; i ++ )
	{
		if(n == checker[i]) return 1;
		bool flag = 1;
		LL x = ksm(checker[i], u, n);
		if(x == 1) continue ;
		for(int j = 0; j < t; j ++ )
		{
			if(x == n - 1)
			{
				flag = 0;
				break ;
			}
			x = mul(x, x, n);
		}
		if(flag) return 0;
	}
	return 1;
}

inline LL f(LL x, LL c, LL n)
{
	LL res = mul(x, x, n) + c;
	return res >= n ? res - n : res;
}
mt19937 mrand(time(0));
inline LL pollard_pho(LL n)
{
	LL x = mrand() % (n - 1) + 1, y = x, c = mrand() % n;
	for(int T = 1; ; T <<= 1)
	{
		LL d = 1;
		y = x;
		for(int i = 0; i < T; i ++ )
		{
			x = f(x, c, n);
			d = mul(d, abs(x - y), n);
			if((i & 127) == 0)
			{
				LL t = __gcd(n, d);
				if(t != 1) return t;
			}
		}
		LL t = __gcd(n, d);
		if(t != 1) return t;
	}
	return 1;
}
inline void find(LL n, LL p[], int &cnt)
{
	if(n == 1) return ;
	if(miller_rabin(n))
	{
		p[ ++ cnt] = n;
		return ;
	}
	LL d = sqrt(n);
	if(d * d == n)
	{
		find(d, p, cnt), find(d, p, cnt);
		return ;
	}
	d = pollard_pho(n);
	while(d == 1 || d == n) d = pollard_pho(n);
	find(d, p, cnt), find(n / d, p, cnt);
}

BSGS

离散对数问题

给定 \(a,b,m\)，满足 \(\gcd(a,m)=1\)，求最小的 \(x\) 满足 \(a^x\equiv b \pmod m\)。

当 \(\gcd(a,m)=1\) 时，\(a\) 存在逆元 \(a^{-1}\)，令 \(S=\sqrt m,x=kS-r\)，则：

枚举 \(r=0\cdots S\)，将 \(a^rb\) 存入哈希表，然后枚举 \(k=1\cdots \lceil \frac{P}{S}\rceil\)，在哈希表中查找 \(a^{kS}\) 对应的最大值，如果存在就找到解。

注意有时候可能满足 \(m\) 是素数但不保证 \(a>0\)，注意特判 \(a\equiv 0\pmod m\) 的情况。

inline LL BSGS(LL a, LL b, LL P)
{
	if(b == 1) return 0;
	LL x = 1, y = 1, s = sqrt(P), t = (P + s - 1) / s;
	unordered_map<int, int> mp;
	for(int i = 0; i < s; i ++ )
	{
		mp[x * b % P] = i;
		x = x * a % P;
	}
	for(int i = 1; i <= t; i ++ )
	{
		y = y * x % P;
		if(mp.count(y)) return i * s - mp[y];
	}
	return -1;
}

如果卡常可以手写哈希，比如

struct uset{
	int key[100007], val[100007];
	inline int find(int x)
	{
		int y = x % 100007;
		while(key[y] && key[y] != x)
		{
			y ++ ;
			if(y == 100007) y = 0;
		}
		return y;
	}
	int sta[100007], tt = 0;
	inline void insert(int x, int d)
	{
		int y = find(x);
		if(!key[y]) sta[ ++ tt] = y;
		key[y] = x, val[y] = d;
	}
	inline void clear()
	{
		while(tt) key[sta[tt]] = val[sta[tt]] = 0, tt -- ;
	}
}mp;
inline LL BSGS(LL a, LL b, LL P)
{
	if(b == 1) return 0;
	LL x = 1, y = 1, s = sqrt(P), t = (P + s - 1) / s;
	mp.clear();
	for(int i = 0; i < s; i ++ )
	{
		mp.insert(x * b % P, i);
		x = x * a % P;
	}
	for(int i = 1; i <= t; i ++ )
	{
		y = y * x % P;
		int t = mp.find(y);
		if(mp.key[t]) return i * s - mp.val[t];
	}
	return -1;
}

BSGS 的本质/广义离散对数问题

一个图，满足每个节点（或涉及到的节点）的入度和初度都是 \(1\)（前驱和后继都是唯一且存在的），求一个点到另一个点的最短距离。

设 \(F_x(a)\) 表示 \(a\) 的 \(x\) 次后继节点，当 \(x<0\) 表示 \(a\) 的 \(x\) 次前驱节点，则需要求最小的 \(x\) 满足 \(F_x(a)=b\)。

类似的可以化成 \(F_{ks}(a)=F_r(b)\)，所以如果可以快速求出 \(F_s(a)\) 就可以用类似的方法解决。

比较常见的有矩阵的幂、置换结合。

另外矩阵乘法，把矩阵哈希乘向量再乘可以减少时间复杂度。

扩展 BSGS

离散对数问题，但是 \(a\) 和 \(m\) 不一定互质。

想办法把它变成互质的，设 \(d=\gcd(a,m)\)，则若 \(b\) 不被 \(d\) 整除说明无解，原方程等价于 \(\dfrac{a}{d}a^{x-1}\equiv \dfrac{b}{d}\pmod {\dfrac{m}{d}}\)。如果仍然不互质，就重复刚才过程。设进行了 \(k\) 次，所有 \(d\) 的积是 \(D\)，则 \(\dfrac{a^k}Da^{x-k}\equiv \dfrac b D \pmod {\dfrac{m}{D}}\)，这时 \(\dfrac{a^k}D\) 存在乘法逆元，可以除过去。注意特判 \(x\leq k\) 的情况。

几个细节：

• 不一定 \(a,b<m\)，所以先要取模。
• 特判的地方：
  • \(m=1\);
  • \(b=1\);
  • \(a=0,b=0\);
  • \(a=0,b\ne 0\)。
• 注意判断 \(x\leq k\) 的解时，模数取原来的 \(m\)，和原来的 \(b\) 比较。
• \(\dfrac{a}{d}\) 可以边做边乘，模数可以取当前的模数。

inline LL exgcd(LL a, LL b, LL &x, LL &y)
{
	if(!b)
	{
		x = 1, y = 0;
		return a;
	}
	LL d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
inline LL inv(LL a, LL P)
{
	a %= P;
	LL x, y;
	exgcd(a, P, x, y);
	return (x % P + P) % P;
}
inline LL exBSGS(LL a, LL b, LL P)
{
	a %= P, b %= P;
	LL OP = P, OB = b;
	if(b == 1 || P == 1) return 0;
	if(a == 0 && b == 0) return 1;
	if(a == 0) return -1;
	LL x = 1, y = 1, k = 0, d;
	while((d = __gcd(a, P)) > 1)
	{
		k ++ ;
		y = y * a % OP;
		if(y == OB) return k;
		x = x * (a / d) % P;
		P /= d;
		if(b % d) return -1;
		b /= d;
	}
	b = b * inv(x, P) % P;
	LL r = BSGS(a, b, P);
	return r == -1 ? -1 : r + k;
}

阶与原根（Primitive Root）

在 \(\Phi_m\) 中，\(\operatorname{ord}(a)\) 表示最小的 \(k>0\) 满足 \(a^k\equiv 1\pmod m\)。

原根 \(g\) 满足 \(\operatorname{ord}(g)=\varphi(m)\)。

性质

• \(a^1,a^2\cdots a^{\operatorname{ord}(a)}\) 两两不同余。由这条性质，可以用原根的若干次方表示 \(\Phi_m\) 中的任意数。
• \(\operatorname{ord}(a)|\varphi(m)\)。
• 若 \(a^k\equiv 1\pmod m\)，则 \(\operatorname{ord}(a)|k\)。
• \(\operatorname{ord}(a^k)=\dfrac{\operatorname{ord}(a)}{\gcd(\operatorname{ord}(a),k)}\)。
• \(m\) 原根存在，当且仅当 \(m=2,4,p^k,2p^k\)，其中 \(p\) 是奇质数。
• 若原根存在，原根个数为 \(\varphi(\varphi(m))\)。
• 若原根存在，最小原根是 \(O(n^{\frac 1 4})\) 的。

求法

枚举 \(d|\varphi(m)\) 求阶。

暴力枚举 \(\gcd(a,m)=1\) 的 \(a\)，判断是否存在 \(\varphi(m)\) 的质因子 \(p\) 满足 \(a^{\frac{\varphi(p)}{p}}\equiv 1 \pmod m\)。

高次同余

求解关于 \(x\) 的方程 \(x^n\equiv b\pmod m\)，且 \(m\) 为奇质数。

设 \(m\) 的一个原根为 \(g\)，可以通过 BSGS 用 \(g^c\) 表示 \(b\)，然后就是线性同余方程 \(ny\equiv c\pmod {\varphi(m)}\)。

斐波那契数列

特征方程

对于二阶递推式 \(a_{n+1}=pa_n+qa_{n-1}\)，求通项。

设 \(a_{n+1}-xa_n=y(a_n-xa_{n-1})\)。

整理得 \(a_{n+1}=(x+y)a_n-xya_{n-1}\)。

根据韦达定理，\(x,y\) 分别是方程 \(x^2-px-q=0\) 的两根。

解出来之后设 \(a_n=sx^n+ty^n\)，代入 \(a_0,a_1\)：

解得

就可以求得通项公式。

用这个方法可以求斐波那契数列通项公式为

一些带根号的题可以试着用一下这个思路，比如有意义的字符串、简单取整问题。

循环节

对于通项公式 \(a_n=\dfrac 1 {\sqrt 5}\left(\left(\dfrac{1+\sqrt 5}2\right)^n-\left(\dfrac{1-\sqrt 5}2\right)^n\right)\)，设 \(X=\left(\dfrac{1+\sqrt 5}2\right),Y=\left(\dfrac{1-\sqrt 5}2\right)\)，讨论 \(\sqrt 5a_n\) 在模 \(P\) 意义下的循环节，设为 \(\pi(P)\)。

对于 \(P\) 是大于 \(5\) 的素数：

当 \(5\) 在模 \(P\) 意义下有二次剩余时，即 \(5^{\frac{P-1}{2}}\equiv1\pmod P\) 时，根据费马小定理，\(X^{P-1}=1,Y^{P-1}=1\)，则存在循环节 \(P-1\)。

当 \(5\) 在模 \(P\) 意义下没有二次剩余时，即 \(5^{\frac{P-1}{2}}\equiv-1\pmod P\) 时，有：

同理 \(X^{P+1}=Y^{P+1}=-1\)。

所以，存在循环节 \(2P+2\)。

特判小质数：

• \(\pi(2)=3\)；
• \(\pi(3)=8\)；
• \(\pi(5)=20\)。

对于 \(p\) 是素数，\(\pi(p^k)=\pi(p)p^{k-1}\)。

设 \(P=\prod p_i^{k_i}\) 是 \(P\) 的质因数分解，则有 \(\pi(P)=\operatorname{lcm}(p_1^{k_1},p_2^{k_2},\cdots)\)。

\(\pi(P)\le6P\)。

线性代数

高斯消元

• 浮点数方程，用绝对值最大的消元，误差最小。
• 异或方程，可以 bitset 优化。
• 自由元：消元过程中，如果这个未知数在后面的方程中均未出现，则这个未知数可以随意取值而不改变方程解的情况。
  • 对于模 \(P\) 意义下的方程，有 \(x\) 个自由元，则解的数量为 \(P^x\)。
  • 高斯消元法会把自由元尽量往后取，如果要最小化解的字典序，从后往前消元，并令所有自由元取 \(0\)。
• 图的随机游走问题
  1. 给定起点、终点，求经过每个点的期望次数：设 \(f_i\) 表示第 \(i\) 个点的期望经过次数，则 \(f_i=\sum_{(j,i)\in E,j\ne t}\frac{f_j}{d_j}+[i==s]\)，求解这个方程。
  2. 给定起点、若干终点，求第一次请过的终点是某个终点的概率：终点只会经过一次，所以概率等于期望经过次数。
  3. 可以证明无论起点在哪里，经过一定次数的游走之后，停在一个点的概率收敛于一个定值，满足 \(f_i=\sum_{(i,j)\in E}\frac{f_j}{d_j}\)。

初等变换

定义初等（行）变换为以下三种操作：

• 交换两行。
• 一行乘以一个非零实数。
• 将一行乘以一个非零实数加到另一行。

矩阵 \(A\in R^{n\times m}\) 的初等行变换可以写成左乘一个 \(T\in R^{n\times n}\) 的方阵。容易构造这样的方阵。

高斯消元的操作都是初等行变换，根据结合律，它可以写成 \(TAx=Tb\)。

类似的定义初等列变换，并且可以写成右乘一个矩阵的形式。

逆矩阵

对矩方阵 \(A\in R^{n\times n}\)，若存在 \(B\in R^{n\times n},AB=BA=I\)，则说 \(A\) 是可逆的，\(B\) 是 \(A\) 的逆矩阵，记作 \(A^{-1}\)。

性质：

• 可逆矩阵逆矩阵唯一：假设不唯一，即 \(A\) 存在两个不同的逆矩阵 \(B,C\)，则 \(B=BI=BAC=C\)，矛盾。
• 可逆矩阵乘积可逆，且 \(AB\) 逆矩阵是 \(B^{-1}A^{-1}\)。
• 全体 \(n\times n\) 的可逆矩阵构成一个群（封闭性，结合律，单位元）。

高斯-约当消元法可以把一个矩阵消成单位阵，所以对 \([A|I]\) 进行高斯-约当消元，可以得到 \([I,A^{-1}]\)。

矩阵的秩

定义矩阵极大线性无关子列向量集的大小为矩阵的列秩，类似的可以定义行秩。

行秩和列秩相等，统称秩，记作 \(\operatorname{rank}(A)\) 或者 \(r(A)\)。

对于方阵，定义满秩为 \(\operatorname{rank}(A)=n\)。行满秩为 \(\operatorname{rank}(A)=n\)，列满秩为 \(\operatorname{rank}(a)=m\)。

具有以下性质：

• \(\operatorname{rank}(A)\leq\min\{n,m\}\)。
• 矩阵满秩等价于矩阵有逆元、以它为系数矩阵的方程有唯一解、可以用单位矩阵通过初等行变换得到。
• 矩阵的秩等于以它为系数矩阵的方程的有效方程数量，未知数数量减自由元数量。
• 乘一个满秩矩阵后，秩不变。
• \(\max\{\operatorname{rank}(A),\operatorname{rank}(B)\}\leq\operatorname{rank}([A|B])\leq\operatorname{rank}(A)+\operatorname{rank}(B)\)。
• \(\operatorname{rank}(A+B)\leq\operatorname{rank}(A)+\operatorname{rank}(B)\)。
• \(\operatorname{rank}(AB)\leq\min\{\operatorname{rank}(A),\operatorname{rank}(B)\}\)。

行列式

定义

展开

定义：

• 子式：任意取 \(k\) 行 \(k\) 列构成的子行列式，称为 \(k\) 阶子式。
• 余子式：\(A_{i,j}\) 表示 \(A\) 去掉第 \(i\) 行和第 \(j\) 列的 \(n-1\) 阶子式。
• 代数余子式：\(M_{i,j}=(-1)^{i+j}A_{i,j}\)。

则

其中第一个等号表示按第 \(j\) 列展开；第二个等号表示按第 \(i\) 行展开。

初等变换对行列式影响

对于初等行变换：

• 交换：一个排列交换两个元素，需要交换相邻元素奇数次，所以交换后行列式的值是原来的相反数。
• \(i\) 行乘 \(k\)：相当于每一项都乘了 \(k\)，所以行列式的值会乘 \(k\)。
• \(i\) 行的 \(k\) 被加到 \(j\) 行：拆成两个行列式之和——原行列式与将 \(j\) 行替换为 \(i\) 行的 \(k\) 倍。将第二个行列式第 \(j\) 行的 \(k\) 提出来，此时出现了两个相同的行，因为交换这两行，行列式的值相等且互为相反数，这个行列式的值为 \(0\)。

列初等变换的性质相同。

由上面的性质，可以得出：行列式不为 \(0\) 等价于矩阵满秩。

另外，矩阵的秩等于最大的 \(k\) 满足 \(k\) 阶子式的行列式不为 \(0\)。

对于上三角阵，行列式的值等于主对角线的乘积。所以可以用高斯消元求行列式。

如果模数不是质数，可以考虑用辗转相除法进行消元，时间复杂度 \(O(n^2(\log m+n))\)。

行列式另一个性质：

对方阵 \(A,B\in R^{n\times n}\)

证明：

\(\det(A)=0\) 时，\(AB\) 一定不满秩，所以成立。

\(\det(A)\ne0\) 时，\(A\) 可以用单位阵通过初等行变换得到，设分别是 \(T_1,T_2\dots T_k\)，则 \(A=\prod T_i\)。

根据上面的性质，对于初等变换矩阵 \(T\) 满足 \(\det(AT)=\det(A)\det(T)\)。

所以 \(\det(A)=\prod\det(T_i),\det(AB)=\prod\det(T_i)\det(B)=\det(A)\det(B)\)。

另外有柯西-比内公式：

对于 \(A\in R^{n\times m},B \in R^{m\times n}\)，有

其中 \(A_S\) 表示 \(A\) 中下标属于 \(S\) 的列组成的矩阵。

范德蒙德行列式：\(A_{i,j}=x_j^{i-1}\) 则

可以证明用它：给定 \(n-1\) 次多项式 \(n\) 个点可以求出这个多项式。

几何意义

对于二阶行列式

表示向量 \((a,b)\) 与向量 \((c,d)\) 或者向量 \((a,c)\) 与向量 \((b,d)\) 的叉积，即两个向量围成三角形的有向面积的 \(2\) 倍。

类似的 \(n\) 阶行列式等于 \(n\) 维空间中，\(n\) 个行向量或者列向量围成广义凸包体的有向体积的 \(n!\) 倍。

Tutte 定理

对图 \(G(V,E)\) 定义 Tutte 矩阵 \(A\)：

其中 \(x_{i,j}\) 是一个变量，且一个 Tutte 矩阵有 \(|E|\) 个变量。

则 \(G\) 的最大匹配等于 \(\operatorname{rank}(A)\)。

实际运用时，可以在取大质数 \(P\) 并在 \(Z_P\) 中随机取值作为 \(x_{i,j}\)。正确率至少为 \(1-\dfrac n P\)，所以一般取 \(10^9\) 级别的质数就足够了。

矩阵树定理

定义：

• 设 \(\#e(i,j)\) 表示边 \((i,j)\) 或 \(<i,j>\) 在 \(E\) 中出现的次数。
• 邻接矩阵:

• 无向图的度数矩阵

• 有向图的入度矩阵

• 有向图的出度矩阵

设 \(A(i)\) 表示 \(A\) 删除 \(i\) 行 \(i\) 列的矩阵，则：

• 无向图的 Kirchhoff 矩阵 \(L=D-A\)，生成树数量等于 \(\det(L(i))\)，\(i\) 为任意满足 \(1\leq i\leq n\) 的值。
• 有向图的外向 Kirchhoff 矩阵 \(L^{out}=D^{in}-A\)，以 \(i\) 为根的外向（叶向）树形图数量等于 \(\det(L(i)^{out})\)。
• 有向图的内向 Kirchhoff 矩阵 \(L^{in}=D^{out}-A\)，以 \(i\) 为根的内向（根向）树形图数量等于 \(\det(L(i)^{in})\)。
• （BEST 定理）有向欧拉图 \(\forall 1\leq i,j\leq n,\det(L^{in}(i))=\det(L^{in}(j))\)，且欧拉回路数量为 \(\det(L^{in}(1))\prod (\operatorname{deg}(i)-1)!\)。
• 无向图欧拉回路计数是 NPC 问题。

常与容斥结合使用。

线性基

处理异或问题的另一个利器。

性质

（异或空间）线性基满足：

• 原集合可以通过异或计算到的所有非零数，也可以用线性基的元素异或计算得到。
• 线性基中的元素异或计算不能得到 \(0\)。
• 线性基中的元素最高位互不相同。
• 线性基的元素个数最小。

插入

把 \(x\) 插入线性基 \(B\)，令 \(B_i\) 表示最高位为 \(i\) 的线性基元素（没有为 \(0\)），则从大到小枚举 \(i\)，对于 \(x\) 有值的一位 \(i\)：

• 如果 \(B_i=0\)，直接插入，\(B_i\gets x\)；
• 如果 \(B_i\ne 0\)，去掉这一位，\(x\gets x\operatorname{xor}B_i\)。

如果最终都没有被插入，说明子集的异或值可以为 \(0\)。

时间复杂度 \(O(m)\)，\(m=\log V\)。

撤销

显然每次操作只会改变 \(1\) 个位置，用栈记录即可。

合并

将一个线性基的元素依次插入另一个即可。

最大子集异或和

从大往小枚举 \(B_i\)，如果当前答案第 \(i\) 位为 \(0\)，则异或。实现可以写成比较大就异或。

最小子集异或和

如果可以是 \(0\) 则答案为 \(0\)，否则为最小的非 \(0\) 的 \(B\)。

\(k\) 小子集异或

先进行重构：

• 从大到小枚举 \(i,j\)，若 \(B_i\) 第 \(j\) 位为 \(1\)，\(B_i\gets B_i\operatorname{xor}B_j\)。
• 把非零的 \(B_i\) 往前移到从零开始连续下标，设有 \(m\) 个，则共有 \(2^m\) 中不同的非零异或和。

然后对于非零的 \(k\) 小异或和，就是 \(k\) 中为 \(1\) 的位的 \(B_j\) 异或和。

最大异或环/路径

一个环是由若干个环异或出来的。可以用 DFS 或者戴荃并查集的方式找环。

一个环异或上任意一条路径则得到一条路径。

最大 XOR 和路径，八纵八横。

戴荃线性基·静态

线性基的加入顺序是可以随便排列的。

线性基会优先保留先加入的元素。

所以，可以按权值排序，然后就能处理加入了。

戴荃线性基·动态

如果在加入时，遇到当前的 \(B_j\) 权值比待加入元素小，则可以将待加入的元素与 \(B_j\) 交换。

运用这个思想，可以实现前缀和线性基、树上差分线性基、带删除线性基。

前缀和线性基

按所处位置为权值，尽量保留位置靠后的，从前往后动态建立线性基，保留其 \(n\) 个版本。

区间 \([l,r]\) 的线性基，即为 \(r\) 版本的权值大于等于 \(l\) 部分。

树上差分线性基

按深度为权值，尽量保留深度较大的，在父亲的版本上加入自己权值构成线性基。

路径 \((u,v)\) 的线性基，即为 \(u,v\) 版本的合并中，深度大于等于 \(deepth_{\operatorname{lca(u,v)}}\) 的部分。

带删除线性基

离线，按删除时间为权值构造线性基，优先保留删除时间大的元素的线性基，当前的线性基即为删除时间大于等于当前时间的部分。

组合数学

容斥

给出二项式反演的公式：

证明：

其它同理。

容斥的另一种形式是：

Burnside 引理

概念

这部分可能不太严谨，如有错误望指出。

• 群：一个集合和一种运算，满足集合内任意两个元素运算的结果在集合内。
• 单位元：群里一个元素，满足它与其它元素运算以及其它元素与它运算都是另一个元素。
• 逆元：与它运算结果是单位元的元素。
• 置换：一个 \(1\sim n\) 到 \(1\sim n\) 的双射。
• 置换乘法：\(A\cdot B=B(A(i))\)，即先执行 \(A\) 置换，再执行 \(B\) 置换的结果。
• 置换群单位元：\(A(i)=i\)。置换群一定有单位元。

内容

对于一个置换长度为 \(n\) 的置换群，定义两个长度为 \(n\) 的序列等价当且仅当其中一个序列可以通过置换群的一些置换操作使序列相等。

序列不等价的方案数为所有置换（包括单位元）操作前后相同的方案数的平均值。

对于带权的情况仍然成立。

模型

环旋转

两个环等价当且仅当可以通过旋转使它们相同，求方案数（设长度为 \(n\) 的环，对应位置不同的方案数为 \(F(n)\)）。

如果加上不旋转这种置换（单位元，也可以当做旋转 \(0\) 个元素），则这些置换构成一个群。

对于旋转 \(k\) 个元素，第 \(i\) 个元素必须与 \(i+k\bmod n,i+2k\bmod n,\cdots\) 值相同，所以每个 \(i\) 与 \(i+\gcd(n,k)\bmod n\) 是相同的，相当于分成长度为 \(\gcd(n,k)\) 的 \(\dfrac{n}{\gcd(n,k)}\) 个相同的段，所以答案为：

几个小技巧：

• 当 \(n\) 是模数倍数时，可以考虑 \(\dfrac{a}{b}\bmod m=\dfrac{a \bmod bm}{b}\)。
• 另外大模数乘法：

LL mul(LL x, LL y, LL m)
{
	LL res = x * y - (LL)((long double)x * y / m + 1e-8) * m;
	return res < 0 ? res + m : res;
}

• 上面是错误示范，早被 nodgd 卡过了，主要原因是也可能多。正确写法如下：

LL mul(LL a, LL b, LL P)
{
	LL res = a * b - (LL)((long double)a * b / P + 1e-8) * P;
	return res < 0 ? res + P : (res >= P ? res - P : res);
}

• 分解质因数之后，预处理每个质因数幂次的值，然后可以运用积性函数的性质，在 dfs 或循环找约数的同时求出 \(\varphi(\dfrac{n}{d})\)。

环翻转

有 \(n\) 种翻转方式，且任意一种先翻转后旋转、两次翻转的方式都可以通过一次翻转完成。

\(n\) 是奇数时，\(n\) 种情况是 \(\dfrac{n-1}{2}\) 个两两一组、\(1\) 个单独一个。

\(n\) 是偶数时，\(\dfrac{n}{2}\) 种情况是 \(\dfrac{n-2}{2}\) 个两两一组、\(2\) 个单独一个，\(\dfrac{n}{2}\) 种情况是 \(\dfrac{n}{2}\) 个两两一组。

正方体

正方体旋转共 \(24\) 种情况：取一个面上画一个箭头，正方体情况不同当且仅当箭头所在面不同或者箭头指向方向不同。

• 不动：\(1\) 种。
• 以对面中心点连线为轴，转 \(1\) 或 \(3\) 次：\(6\) 种。
• 以对面中心点连线为轴，转 \(2\) 次：\(3\) 种。
• 以对楞中点连线为轴，转 \(1\) 次：\(6\) 种。
• 以对顶点连线为轴，转 \(1\) 或 \(2\) 次：\(8\) 种。

弄一个正方体，手动旋转看循环数量。

小结

很多难题 Burnside 引理只是其中一小部分，重要的还是后面算方案数。

数值算法

拉格朗日插值

已知关于 \(x\) 的 \(n\) 次多项式 \(F(x)\)，满足 \(n+1\) 个条件 \(F(x_i)=y_i(0\le i\le n)\)，求多项式。

构造多项式 \(F_i(x)\) 满足

则

所以

一般是用来求值的，所以把值代入即可。

分子部分可以通过前后缀积或者全部除以单个计算，对于分母部分，如果数值是连续的就可以转化为两个阶乘之积，注意符号。

本栏目推荐文章
• [oeasy]python0004_游乐场_和python一起玩耍_python解释器_数学运算
• 在算法比赛中的常用数学库函数
• 数学基础(一)-标量、向量、矩阵、张量以及各范数的含义
• 数学家候选人
• 速通 离散数学(1)
• 具体数学第六章习题选做（genshining）
• 数学与通信
• 利用JavaScript函数进行数学计算和逻辑判断
• Github page数学公式无法正常显示解决方案(MathJax)
• 2023-2024清华附中一道初三数学新定义题的详细题解

数学数学题 数学分析 数学amp 数学家 数学math 数学基础 数学试卷 数学学习 组合数学 数学建模