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^1(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^2(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 \le n, m \leq {10}^6$。

思考以下构造，对于一个 $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)\times G(x_i))$，所以我们现在需要一个算法快速找出 $n+m+1$ 个函数的点值。

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

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

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

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

$$F(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6+a_7x^7$$

按照次数的奇偶来分成两组，然后右边提出来一个 $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\left(x^2\right) + x \times H\left(x^2\right)$$

利用偶数次单位根的性质 $\omega^i_n = -\omega^{i + n/2}_n$，和 $G\left(x^2\right)$ 和 $H\left(x^2\right)$ 是偶函数，我们知道在复平面上 $\omega^i_n$ 和 $\omega^{i+n/2}_n$ 的 $G(x^2)$ 的 $H(x^2)$ 对应的值相同。得到：

$$\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(\omega_{n/2}^k)$ 和 $H(\omega_{n/2}^k)$ 后，就可以同时求出 $F(\omega_n^k)$ 和 $F(\omega_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)$$

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

证明

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

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

$$\sum_{g \in G} \mathrm{Fix}(g) = \sum_{x \in X} |\text{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$，根据轨道 - 稳定化子定理可知：

$$\sum_{x \in O_i} |\text{Stab}(x)| = |G|.$$

所有轨道的贡献总和为 $N \cdot |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$ 种颜色可供选择，所以总的不动点数为：

$$\mathrm{Fix}(g) = m^{c(g)}.$$

将 $\mathrm{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 \leftarrow k$ 并结束扫描，如果存在，令 $k\leftarrow k~\text{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$ 的一组向量若满足

1. 线性无关

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

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

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

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

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

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