Math

2025年7月13日
分类于 Math
需要 2 分钟阅读时间

群论基础

定义

定义集合 $G$ 与在 $G$ 上的二元运算 $\times$，若其满足以下条件，则称 $(G,\times)$ 为一个群。

封闭性。$\forall a,b \in G,a \times b \in G$
结合性。$\forall a,b,c \in G,(a \times b) \times c = a \times (b \times c)$
单位元存在性。$\exists e \in G,\forall a \in G,e \times a = a \times e = a$
逆元存在性。$\forall a \in G,\exists b \in G,a \times b = b \times a = e$

性质

单位元唯一

$e_1 \times e_2 = e_1 = e_2$

逆元唯一

设 $a$ 有逆元 $b,c$，$c \times a \times b = e \times b = c \times e = b = c$

关于子群 & 陪集

对于群 $(G,\times)$，若 $H \subseteq G$，且 $(H,\times)$ 构成一个群，则称 $(H,\times)$ 为 $(G,\times)$ 的子群，简记为 $H \le G$。

对于 $H \le G,g \in G$，定义 $gH=\{g \times h \mid h \in H\}$，称为 $H$ 关于 $g$ 的左陪集。右陪集同理。

下面是陪集的若干性质。

$\forall g \in G, |gH| = |H|$
$\forall g \in G, g \in gH$ （这是因为 $e \in H$）
$gH = H \iff g \in H$
$aH = bH \iff b ^{-1} \times a \in H$
$aH \cap bH \not = \emptyset \Rightarrow aH = bH$
$H$ 所有的陪集并为 $G$。

Proof

(3) $g \in H \Rightarrow gH = H$，$g \not \in H, g \in gH \Rightarrow gH \not = H$

(4) $aH = bH \Rightarrow b^{-1} \times a H = H \Rightarrow b^{-1} \times a \in H$

(5) $aH \cap bH \not = \emptyset \Rightarrow \exists x,y \in H, ax = by \Rightarrow x \times y^{-1} = b\times a^{-1} \in H \Rightarrow aH = bH$

一些表述：

对于 $H \le G$，$G / H$ 表示 $G$ 中 $H$ 所有的左陪集 $\{gH \mid g \in G\}$。

对于 $H \le G$，$[G : H]$ 表示 $G$ 中 $H$ 不同陪集的数量。

关于记号

以下将群 $(G,\times)$ 简记为 $G$。

拉格朗日定理

对于有限群 $G$ 及其子群 $H$，有

\[ |H| \times [G:H] = |G| \]

即 $H$ 的阶乘 $G$ 中 $H$ 不同陪集的数量等于 $G$ 的阶。

理解：因为 $H$ 的所有陪集不交，大小都为 $|H|$，且并为 $G$，故不同的陪集有 $\frac { |G| } { |H| }$ 个。

群作用

对于群 $G$ 和集合 $X$，$G$ 中每个元素都是 $X$ 到自身的映射，记 $g \in G$ 将 $x \in X$ 映射为 $g(x)$，若所有映射满足以下条件，那么称群 $G$ 作用于集合 $X$ 上。

结合律。$\forall g_1,g_2 \in G,x \in X,g_1(g_2(x)) = (g_1 \times g_2)(x)$
单位元是恒等变换。$\forall x \in X,e(x) = x$

轨道-稳定子定理

对于群 $G$ 作用在集合 $X$ 上，称 $x \in X$ 的稳定子为 $G^x = \{g \mid g \in G, g(x) = x\}$，轨道为 $G(x) = \{g(x) \mid g \in G\}$。

定理内容：

\[ \forall x \in X, |G^x| \times |G(x)| = |G| \]

即任意 $X$ 中的元素，其轨道和稳定子的大小之积为群 $G$ 的阶。

考虑证明 $G^x$ 为 $G$ 的子群

首先有 $e \in G^x$

封闭性：对于 $\forall a,b \in G^x$，有 $a(x) = b(x) = x$，再根据 $a(b(x)) = (a \times b) (x)$，有 $a \times b \in G^x$。

结合性显然。

逆元：对于 $g \in G^x$，有 $g^{-1}(g(x))=(g^{-1} \times g)(x) = e(x) = x$，故 $g^{-1} \in G^x$。

故根据拉格朗日定理我们只需证明 $|G(x)|=[G:G^x]$。

2025年2月22日
分类于 Math
需要 3 分钟阅读时间

单位根相关

复数域下方程 $x^n = 1$ 恰好有 $n$ 个解，记 $\omega_n = e^{\frac {2 \text{i} \pi} n}$，则这 $n$ 个解恰好为 $1,\omega_n,\omega_n^2,\cdots,\omega_n^{n-1}$。我们将 $\omega_n$ 称作 $n$ 次单位根。

在运算中，有 $\omega_n = e^{\frac {2 \text{i} \pi} n} = \cos \frac {2 \pi} n + \text{i} \sin \frac{2 \pi} n$。

特别地，在模 $P$ 意义的数域下，有 $\omega_n \equiv g^{\frac {P-1} n} \pmod P$，其中 $g$ 是模 $P$ 意义下的原根。

基础公式

Lemma 1

\[ \sum _{i=0} ^{n-1} \omega_n^i = [n=1] \]

这是因为根据等比数列求和公式有原式 $= \frac{1 - \omega_n^n} {1 - \omega_n}$，当 $n>1$ 时该式分子为零分母不为零，当 $n=1$ 时原式等于 $1$。

Lemma 2

\[ [n|k] = \frac 1 n \sum _{i=0} ^{n-1} \omega _n ^{ik} \]

证明

当 $n|k$ 时，原式显然成立。
当 $n \nmid k$ 时，有 $\omega_n ^k \not = 1$，根据等比数列求和公式有 $$ \sum _{i=0} ^{n-1} \omega _n ^{ik} = \frac {1 - \omega_n ^{kn}} {1 - \omega_n ^k} = 0 $$

注意到 Lemma 1 是 Lemma 2 $k=1$ 时的特例。

Lemma 3

\[ [k \equiv a \pmod n] = \frac 1 n \sum_{i=0}^{n-1} \omega_n^{i(k-a)} \]

这是因为 $k \equiv a \pmod n \iff n \mid (k-a)$。

Lemma 2 和 Lemma 3 是 单位根反演 的重要公式。

单位根反演

设有多项式 $f(x)$，现在我们要求它在 $d$ 的倍数处的系数和，即 $\sum_{d \mid i} [x^i]f(x)$，但是难以求出这个多项式的系数序列，甚至是无限长的。这是我们就要用到单位根反演。

基本形式

$\sum_{d \mid i} [x^i]f(x) = \frac 1 d \sum_{i=0}^{d-1} f(\omega_d ^i)$。

证明考虑设 $f(x) = \sum _{i \ge 0} a_i x^i$，考虑对于一位 $a_j$，它贡献答案的系数为 $\sum _{i=0} ^{d-1} \omega_d ^{ij}$，根据 Lemma 2 这个式子等于 $d[d|j]$，因此原式易得。

由此以及 Lemma 3 我们容易得到更一般的形式：

\[ \sum _{i \equiv a \pmod n} [x^i] f(x) = \frac 1 n\sum _{i=0} ^{n-1} \omega_n ^{-ia} f(\omega_n ^i) \]

例题

LOJ 6485

给定 $n,s,a_{[0,4)}$，求

\[ \sum _{i=0} ^n \binom {n} {i} s^i a_{i \bmod 4} \]

solution

容易想到对于 $i \in [0,4)$ 分开统计贡献，我们由系数序列 $f_i = \binom n i s^i$ 得到函数 $f(x) = (1+xs)^n$，由单位根反演的基本形式容易在 $O(\log n)$ 内解决。

推荐例题：QOJ5370。

Luogu P5591

给定 $n,p,k$，询问

\[ \sum_{i=0}^n \binom n i \times p^{i} \times \left\lfloor \frac{i}{k} \right\rfloor \bmod 998244353 \]

保证 $k$ 是 $2$ 的 $[0,20]$ 次幂。

hint

$\left\lfloor \frac{i}{k} \right\rfloor = \frac {i - (i \bmod k)} k$

solution

将答案拆成 $\sum_i \binom n i p^i i$ 和 $\sum_i \binom n i p^i (i \bmod k)$ 两部分。

对于第一部分，我们有 $\binom n m = \frac n m \binom {n-1} {m-1}$，因此

\[ \begin{aligned} \sum_{i=0} ^n \binom n i p^i i & = n \sum_i \binom {n-1} {i-1} p ^i \\ & = n p (1 + p) ^{n-1} \\ \end{aligned} \]

最后一步由二项式定理易得。

第二部分使用单位根反演，对于 $i \in [0,k)$ 计算系数：

\[ \begin{aligned} \sum_{i=0} ^n \binom n i p^i (i \bmod k) & = \sum _{i=0} ^{k-1} i \sum_{j=0} ^n [i \equiv j \pmod k] \binom n j p^j \\ & = \sum _{i=0} ^{k-1} i \sum_{j=0} ^n \sum_{t=0} ^{k-1} \omega_k^{t(j-i)} \binom n j p^j \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it}\sum_{j=0} ^n \omega_k^{tj} \binom n j p^j \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it}\sum_{j=0} ^n \binom n j (\omega_k^tp)^j \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it} (1 + \omega_k^t p)^n \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it} g(t) & \bigg(g(x) = (1 + \omega_k^x p)^n \bigg) \\ & = \sum _{i=0} ^{k-1} i f(\omega_k^{-i}) & \bigg(f(x) = \sum_{i=0} ^{k-1} g(i)x^i\bigg) \\ \end{aligned} \]

算式中的 $g(x)$ 我们可以在 $O(k \log n)$ 的时间内求出，而对于求 $f$ 在单位根处的点值，我们可以通过 NTT 在 $O(k \log k)$ 时间内求出，总时间复杂度 $O(k(\log k + \log n))$。

当然本题还有更简单的做法，即在公式倒数第二步交换 $i,t$ 的求和顺序，然后就是求一个 $S(n,x) = \sum_{i=0} ^n i x^i$，可以用类似等比数列求和的技巧做到 $O(\log n)$ 时间内求解。

Luogu P10664

给定整数 $n,k,p$，要求计算下列式子对 $p$ 取模的值：

\[\sum_{i=0}^n [k|i] \binom n {i} F_{i}\]

其中：

$p$ 为质数，且 $p$ 除以 $k$ 的余数为 $1$。
$F_n$ 为斐波那契数列，即 $F_0=1$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$。

hint

Fibonacci 数列看起来很棘手，难以将其转化为多项式函数。

但是别忘了它可以用矩阵快速幂计算，我们可以将函数变为从矩阵到矩阵的映射，从而将 $F_i$ 变成 $x^i$。

solution

先忽略 $k$ 的限制，我们要求 $\sum_i \binom n i F_i$。

我们设 Fibonacci 转移矩阵为 $X$，则原式为 $(I + X)^n$。

最后设 $f(x)=(I+Xx)^n$ 即可使用单位根反演快速计算。

注意 $n$ 要开到 long long 范围。

参考

2024年7月31日
分类于 Math
需要 5 分钟阅读时间

行列式

定义

定义 $n$ 阶方阵 $A$ 的行列式为：

\[ \det A=\begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} =\sum_{p_1,p_2,\cdots,p_n} (-1)^{\tau(p_1,p_2,\cdots,p_n)} \prod_{i=1}^n a_{i,p_i} \]

其中 $\{p_1,p_2,\cdots,p_n\}$ 是一个 $n$ 的排列，$\tau(p_1,p_2,\cdots,p_n)$ 表示 $\{p_1,p_2,\cdots,p_n\}$ 的逆序数。

引理

Lemma 1

\[ \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ ka_{i,1} & ka_{i,2} & \cdots & ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = k \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

读者自证不难。

Lemma 2

\[ \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = -\begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

读者自证不难。

Lemma 3

若矩阵有相同的两行，则行列式为零。

Proof: 交换相同的两行后矩阵不变，且由 Lemma 2 得行列式变号，即 $|A|=-|A|$，所以 $|A|=0$。$\square$

Lemma 4

若矩阵某一行是另一行的倍数，则行列式为零。

Proof: 由 Lemma 1 & Lemma 3 易证。

Lemma 5

若 $\forall j,a_{i,j} = b_j + c_j$，则

\[ \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ b_1 & b_2 & \cdots & b_n \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} + \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ c_1 & c_2 & \cdots & c_n \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

读者自证不难。

Lemma 6

\[ \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1}+ka_{i,1} & a_{j,2}+ka_{i,2} & \cdots & a_{j,n}+ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

Proof: 设

\[ A = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}, B = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ ka_{i,1} & ka_{i,2} & \cdots & ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \\ C = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1}+ka_{i,1} & a_{j,2}+ka_{i,2} & \cdots & a_{j,n}+ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

由 Lemma 4 得 $|B|=0$，由 Lemma 5 得 $|C| = |A| + |B| = |A|$。$\square$

Lemma 7

\[ \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ 0 & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{n,n} \\ \end{vmatrix} = \prod_i a_{i,i} \]

即上三角矩阵的行列式为主对角线元素的乘积。

Proof: 由行列式的定义得若 $\exists i, a_{i,p_i} = 0$，那么整个排列对行列式无贡献。

因此要想对行列式有贡献，$p_n$ 必等于 $n$，同理得 $\forall i, p_i = i$。$\square$

求解

显然有 $\mathrm O(n! n)$ 的 naive 方法，但如果这样上面的 $\LaTeX$ 就白写了（

考虑把矩阵转化为上三角矩阵并由 Lemma 7 $\mathrm O(n)$ 计算行列式。

这个过程形如高斯消元，于是考虑用高斯消元法来求解行列式。

假设目前处理到第 $i$ 行，要使得 $\forall j > i, a_{j,i} = 0$。

显然可以让第 $j$ 行加上第 $i$ 行乘 $- \frac{a_{i,j}}{a_{i,i}}$，但对于任意模数情况下 $a_{i,i}$ 不一定有逆元。

因此，我们考虑用辗转相除法。

每次使得 $a_{j,i} \gets a_{j,i} \bmod a_{i,i}$，并交换第 $i$ 行与第 $j$ 行，直到 $a_{i,i}$ 为 $0$。

即让第 $j$ 行加上第 $i$ 行乘 $- \lfloor \frac{a_{i,j}}{a_{i,i}} \rfloor$。

时间复杂度看似是 $\mathrm O(n^3 \log P)$，但可以证明是 $\mathrm O(n^3)$，其中 $P$ 是模数。

参考代码

C++

int n,p,a[N + 2][N + 2];
int det() {
    int sgn=0;
    for(int i=1; i<=n; ++i)
        for(int j=i+1; j<=n; ++j) {
            while(a[i][i]) {
                ll d=a[j][i]/a[i][i];
                for(int k=1; k<=n; ++k)
                    a[j][k]=(a[j][k]-d*a[i][k]%p)%p;
                swap(a[i],a[j]);
                sgn^=1;
            }
            swap(a[i],a[j]);
            sgn^=1;
        }
    ll ans=sgn?-1:1;
    for(int i=1; i<=n; ++i) ans=ans*a[i][i]%p;
    return (ans+p)%p;
}

应用

矩阵树定理

2024年7月10日
分类于 Math
需要 1 分钟阅读时间

数学

这里是一些数学相关的算法。

线性代数
- 行列式
单位根相关