2025 春季数论

幂

上升幂

上升阶乘幂 $\displaystyle x^{\overline{n}}=\prod_{k=0}^{n-1} (x+k)$。

下降幂

下降阶乘幂 $\displaystyle x^{\underline{n}}=\prod_{k=0}^{n-1} (x-k)$。

斯特林函数

一类

定义

第一类斯特林数（斯特林轮换数）~~（斯大林数）~~ $\begin{bmatrix}n\\ k\end{bmatrix}$，也（不知道可不）可记做 S¹(n, k)，表示将 n 个两两不同的元素，划分为 k 个互不区分的非空圆排列（轮换）的方案数。

递推式

$$ \begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix} $$

边界是 $\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]$。

证明显然，读者自证不难。

上升幂转普通幂：

$$ x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k $$

下降幂转普通幂：

$$ x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k $$

二类

第二类斯特林数（斯特林子集数）~~（斯二林数）~~ $\begin{Bmatrix}n\\ k\end{Bmatrix}$，也（不知道可不）可记做 S²(n, k)，表示将 n 个两两不同的元素，划分为 k 个互不区分的非空子集的方案数。

递推式

$$ \begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix} $$

边界是 $\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]$。

证明显然。

普通幂转上升幂：

$$ x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}} $$

普通幂转下降幂：

$$ x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}} $$

斯特林反演

定义

$$ f(n)=\sum_{k=0}^{n}\begin{Bmatrix}n\\ k\end{Bmatrix}g(k)\iff g(n)=\sum_{k=0}^{n} (−1)^{n−k}\begin{bmatrix}n\\ k\end{bmatrix}f(k) $$

二项式反演

定义

$$ g(n)=\sum_{i=0}^{n}\dbinom{n}{i}f(i) \\ \iff \\ f(n)=\sum_{i=0}^{n}\dbinom{n}{i}(-1)^{n-i}g(i) $$

多项式卷积

FFT

给定一个 n 次多项式 F(x)，和一个 m 次多项式 G(x)。

请求出 F(x) 和 G(x) 的卷积。

1 ≤ n, m ≤ 10⁶。

思考以下构造，对于一个 n − 1 次多项式 $\displaystyle F(x)=\sum_{i=0}^{n-1}a_ix^i$，我们只需要找到 n 个互不相同的点 (x_i, y_i)，那么就可以唯一确定地构造出这个函数。

而两个函数的卷积，假设结果为 H(i)，那么就一定可以找出 n + m + 1 个点来构造出它，这些点是 (x_i, F(x_i) × G(x_i))，所以我们现在需要一个算法快速找出 n + m + 1 个函数的点值。

FFT（快速傅里叶变换），可以在 Θ(nlog n) 的时间复杂度内求解。

思路：我们可以不局限于实数域内，把目光放到复数域内，考虑将单位根带入 F, G。

FFT 算法的基本思想是分治。它分治地来求当 x = ω_n^k 的时候 F(x) 的值。FFT 的分治思想体现在将多项式分为奇次项和偶次项处理。

举个例子，对于一共 8 项的多项式：

F(x) = a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ + a₅x⁵ + a₆x⁶ + a₇x⁷

按照次数的奇偶来分成两组，然后右边提出来一个 x：

$$ \begin{aligned} F(x) &= (a_0+a_2x^2+a_4x^4+a_6x^6) + (a_1x+a_3x^3+a_5x^5+a_7x^7)\\ &= (a_0+a_2x^2+a_4x^4+a_6x^6) + x(a_1+a_3x^2+a_5x^4+a_7x^6) \end{aligned} $$

分别用奇偶次次项数建立新的函数：

$$ \begin{aligned} G(x) &= a_0+a_2x+a_4x^2+a_6x^3\\ H(x) &= a_1+a_3x+a_5x^2+a_7x^3 \end{aligned} $$

那么原来的 F(x) 用新函数表示为：

F(x) = G(x²) + x × H(x²)

利用偶数次单位根的性质 ω_nⁱ = −ω_n^i + n/2，和 G(x²) 和 H(x²) 是偶函数，我们知道在复平面上 ω_nⁱ 和 ω_n^i + n/2 的 G(x²) 的 H(x²) 对应的值相同。得到：

$$ \begin{aligned} F(\omega_n^k) &= G((\omega_n^k)^2) + \omega_n^k \times H((\omega_n^k)^2) \\ &= G(\omega_n^{2k}) + \omega_n^k \times H(\omega_n^{2k}) \\ &= G(\omega_{n/2}^k) + \omega_n^k \times H(\omega_{n/2}^k) \end{aligned} $$

和：

$$ \begin{aligned} F(\omega_n^{k+n/2}) &= G(\omega_n^{2k+n}) + \omega_n^{k+n/2} \times H(\omega_n^{2k+n}) \\ &= G(\omega_n^{2k}) - \omega_n^k \times H(\omega_n^{2k}) \\ &= G(\omega_{n/2}^k) - \omega_n^k \times H(\omega_{n/2}^k) \end{aligned} $$

因此我们求出了 G(ω_n/2^k) 和 H(ω_n/2^k) 后，就可以同时求出 F(ω_n^k) 和 F(ω_n^k + n/2)。于是对 G 和 H 分别递归即可。

NTT

和 FFT 没什么区别。FFT 很大的问题是没法取模（因为用了大量复数和浮点数），NTT 解决了这个问题。

NTT 试图在整数域内寻找这样的根，实际上在同余意义下确实有这样的数，它就是原根。

原根是什么？简单来说，就是多次次方以后可以覆盖完整个简化剩余系的数。

举个例子。

$$ \begin{aligned} 3^0 \equiv 1 \pmod 7\\ 3^1 \equiv 3 \pmod 7\\ 3^2 \equiv 2 \pmod 7\\ 3^3 \equiv 6 \pmod 7\\ 3^4 \equiv 4 \pmod 7\\ 3^5 \equiv 5 \pmod 7\\ 3^6 \equiv 1 \pmod 7\\ \cdots\cdots\cdots\cdots\cdots\cdots \end{aligned} $$

所以 3 就是 7 的一个原根。

显然，它具有单位根的种种性质，使得它可以在模意义下代替单位根。

Polya 定理与 Burnside 引理

Burnside 引理

定义

Burnside 引理主要用于计算群作用下的轨道数目。假设存在一个有限群 G 作用于集合 X，那么不同等价类的数量可以通过以下公式计算：

$$ N = \frac{1}{|G|} \sum_{g \in G} \mathrm{Fix}(g) $$

这里的 Fix(g) 指的是集合 X 中在置换 g 作用下保持不变的元素（也就是不动点）的个数。

证明

对于集合 X 中的任意元素 x，其等价类的大小为 $|G.x| = \frac{|G|}{|\text{Stab}(x)|}$。其中，Stab(x) = {g ∈ G ∣ g(x) = x} 表示元素 x 的不动点集合。

我们来统计所有满足 g(x) = x 的 (g, x) 对。可以得到：

∑_g ∈ GFix(g) = ∑_x ∈ X|Stab(x)|.

接着，我们将集合 X 按照轨道进行分解，可表示为 $X = \bigcup_{i=1}^N O_i$。那么就有：

$$ \sum_{x \in X} |\text{Stab}(x)| = \sum_{i=1}^N \sum_{x \in O_i} |\text{Stab}(x)|. $$

对于每一个轨道 O_i，根据轨道 - 稳定化子定理可知：

∑_{x ∈ O_i}|Stab(x)| = |G|.

所有轨道的贡献总和为 N ⋅ |G|，将其代入前面双重计数的结果中，就可以得到：

$$ \sum_{g \in G} \mathrm{Fix}(g) = N \cdot |G| \implies N = \frac{1}{|G|} \sum_{g \in G} \mathrm{Fix}(g). $$

Polya 定理

定义

Polya 定理实际上是 Burnside 引理在染色问题中的具体应用。设 G 是作用在 n 个对象上的置换群，使用 m 种颜色对这些对象进行染色，那么不同的染色方案数可以通过以下公式计算：

$$ \frac{1}{|G|} \sum_{g \in G} m^{c(g)} $$

其中，c(g) 表示置换 g 的循环节数，也就是将置换分解为不相交轮换的个数。

例如，对于正六边形的旋转群，其每个置换都对应着不同的旋转角度，我们只需计算出每个置换的循环数，然后代入上述公式即可。

证明

对于置换群 G 中的每一个置换 g，都可以将其分解为 c(g) 个不相交的轮换。例如，旋转 60° 对应的就是一个 6 - 轮换。需要注意的是，在轮换内的对象位置必须同步变动。

一个染色方案在置换 g 作用下保持不变的充要条件是，每个轮换内的对象颜色都相同。

下面举例说明：若置换 g 可以分解为 2 个轮换，且这两个轮换的长度均为 3，那么在染色时，第一个轮换内的所有对象颜色必须相同，第二个轮换内的所有对象颜色也必须相同。

由于每个轮换都有 m 种颜色可供选择，所以总的不动点数为：

Fix(g) = m^c(g).

将 Fix(g) = m^c(g) 代入 Burnside 公式，就能够得到：

$$ N = \frac{1}{|G|} \sum_{g \in G} m^{c(g)}. $$

线性基

前言

由于基以及线性基的概念过于抽象，我无法完全理解，所以我将针对某一道确切的题目来进行阐述。

定义

例如针对这道异或线性基的题来说吧。

我们假设一个数列 A 中元素相互异或可以表示出来的值有另一个集合 B 也可以表述出来，且 B 满足一下性质。

线性无关（即任意非空子集的异或和不为 0）
对 A 中的任意元素 x，都可在 B 中取出若干元素使其异或和为 x
对任意满足上两条的集合 B^′，其元素个数不会小于 B 的元素个数。

用途

判断一个数能否表示成某数集子集的异或和；
求一个数表示成某数集子集异或和的方案数；
求某数集子集的最大/最小/第 k 大/第 k 小异或和；
求一个数在某数集子集异或和中的排名。

构造

具体来说怎么构造呢？

容易发现，线性基内的每一个数的最高位 1 的位置是不重的（重了的就可以把它们俩异或一下），所以我们可以记录每一个最高位对应那个线性基元素。

具体来说，对原集合的每个数 k 转为二进制，从高位向低位扫，对于第 i 位是 1 的，如果 p_i 不存在，那么令 p_i ← k 并结束扫描，如果存在，令 k ← k xor p_i。

或者使用高斯消元的方式来构建线性基，这样构建出来的线性基就是有一些很好的性质，于是我们考虑如何将贪心构造的线性基转化为高斯消元的线性基。

观察得到，我们显然可以对着最后的贪心得到的线性基进行一遍消元，然后就可以了。

那它有什么神奇的性质要我们这么做呢？比如我们可以对于某一个给定的 k，对它进行二进制分位，可以发现如果第 i 位为 1，那么就异或上 p_i 最后得到的就是第 k 小的异或值。

证明显然。

对着代码可能好理解一点。

#include<bits/stdc++.h>
using namespace std;
int n, a[50], d[50];
int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) {
		bitset<50> b;
		b = a[i];
		for (int j = 49; j >= 0; --j) {
			if (b[j]) {
				if (!d[j]) {
					d[j] = a[i];
					break;
				}
				b ^= d[j];
			}
		}
	}
	int ans = 0;
	for (int i = 49; i >= 0; --i) {
		if ((ans ^ d[i]) > ans) ans ^= d[i];
	}
	cout << ans << endl;
	return 0;
}

至于基和线性基具体是什么，那么我们可能得扯一点数学的概念了。

在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

向量空间 V 的一组向量若满足

线性无关

V 中任一向量可由此向量线性表出

则称该组向量是 V 中的一个基（亦称基底）。

一个向量空间的基有很多，但每个基所含向量个数却是个定数。

其实在我个人看来，向量空间和群有挺高的相似度的，而基就相当于剩余系中的简化剩余系（不恰当比喻+=2）

线性表出意味着什么呢，就是通过对基内向量的放缩，再进行加法，就可以表示线性空间内的所有量的话，它就是向量空间的一个基。

但是，我们并不需要搞那么复杂，OI 中有关线性基的应用一般只涉及两类线性空间：n 维实数域线性空间 Rⁿ 和 n 维布尔域线性空间 Z₂ⁿ。

#数学

2025 春季数论

https://lzj-blog.top/2025/03/14/2025 春季数论/

作者

lzj

发布于

2025年3月14日

许可协议

Prufer 序列上一篇

wordgame 题解（不了一点）下一篇