数学大礼包

线性代数

矩阵加速

题目链接

考虑构造一个 $1\times 3$ 的向量 $$f(n)$$ ，代表为 $[a_n,a_{n-1},a_{n-2}]$ ，考虑怎么从 $$f(n-1)$$ 这个状态转移过来。注意到，有

\begin{bmatrix} a_n \\ a_{n-1} \\ a_{n-2} \\ \end{bmatrix} = \begin{bmatrix} 1&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix} \times \begin{bmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \end{bmatrix}

类推可得：

\begin{bmatrix} a_n \\ a_{n-1} \\ a_{n-2} \\ \end{bmatrix} = \begin{bmatrix} 1&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}^{n} \times \begin{bmatrix} 1 \\ 1 \\ 1 \\ \end{bmatrix}

进行快速幂即可

高斯消元

题目链接

考虑把题目中的式子转化为如下的增广矩阵

\left[ \begin{array}{ccccc|c} a_{11} & a_{12} & a_{13} &… &a_{1n} & b_1 \\ a_{21} & a_{22} & a_{23} &… &a_{2n}& b_2 \\ a_{31} & a_{32} & a_{33} &… &a_{3n}& b_3 \\ … a_{n1} & a_{n2} & a_{n3} &… &a_{nn}& b_n \end{array} \right]

枚举 $$i$$ 从 $$1$$ 到 $$n$$ ，然后对 $$i$$ 列，找到 $i\sim n$ 中值最大的，和第 $$i$$ 行交换，然后用这一行的值去消掉其他每行第 $$i$$ 列的值，如果某一次 $i\sim n$ 中的值全为 $$0$$ ，说明方程无解或有无穷解，返回No Solution

模板线性基

线性基的定义：

对一个集合A中的所有元素，找出一个子集B，使得A中所有元素都可以通过 B 中元素异或得到

注意到，线性基有如下性质

线性基是原集合的一个极大线性无关组
等价性
极小性
无零子集性
集合大小固定

对于集合大小固定，需要特别阐明：

感性理解：对于向量空间 $$V$$ 的描述，需要固定多个基向量来张成整个空间

严谨证明：

考虑对向量空间 $$V$$ ，存在两组基： $A={a_1,a_2,...,a_m}$ 和 $$B = b_1,b_2,...,b_n$$ ，我们证明 $$m=n$$

先证明 $m \le n$ : 因为 $$A$$ 是基，所以它能张成 $$V$$ 意味着 $$B$$ 中所有的 $$n$$ 个向量都可以由 $$A$$ 线性表示。如果 $$m > n$$ 那么在 $\mathbb{R}^m$ 空间内， $$n$$ 个向量( $$B$$ 的坐标表示)不可能张成整个 $$m$$ 维空间（因为 $$n<m$$ ），这会导致 $$A$$ 中的某个向量无法由 $$B$$ 张成，与" $$B$$ 也是基"矛盾。严谨的，使用Steinitz 交换引理：我们可以用 $$B$$ 中的向量逐个替换 $$A$$ 中的向量而保持张成空间不变，最终 $$A$$ 中所有 $$m$$ 个向量都能被 $$B$$ 替换掉，这意味着 $$B$$ 中至少要有 $$m$$ 个向量，即 $m\le n$
同理可证 $n\le m$ : 反过来，用 $$A$$ 替换 $$B$$ ，可得 $m\ge n$

因此，只能得出 $$m=n$$ 。

in short:线性基就是用最少的数，保留原集合所有异或可能性

线性基的构造：

我们考虑维护一个数组 p[i]，表示最高位在第i位的基向量

约束：线性基中所有数的二进制最高位互不相同

插入(insert)

void insert(long long x) {
    for (int i = 60; i >= 0; i--) {   // 从高位到低位枚举
        if (!(x >> i & 1)) continue;  // 第 i 位是 0，跳过
  
        if (!p[i]) {   // 这一位还没有基向量
            p[i] = x;  // 直接放入
            return;
        }
  
        x ^= p[i];     // 用已有的基向量消去当前位
    }
    // 如果 x 变成 0，说明它可由已有基向量异或得到，舍弃
}

查询异最大异或和(query)

考虑直接进行贪心

long long query_max() {
    long long res = 0;
    for (int i = 60; i >= 0; i--) {
        if ((res ^ p[i]) > res) {
            res ^= p[i];
        }
    }
    return res;
}

P3857 [TJOI2008] 彩灯

给定m个长度为n的01串，这些01串任意异或，求可以得到多少不同01串。答案对2008取模（ $n,m\le 50,n,m\in Z_+$ ）

考虑把01串转化为正数（开long long），然后计算其线性基。假设存在 $$cnt$$ 个线性基，答案即 $2^{cnt} \mod 2008$

P4570 [BJWC2011] 元素

给定 $$n$$ 个二元组{ $$id,val$$ }，要求找出一个子集，满足 $$id$$ 异或和不为0,且 $\sum val$ 最大

考虑贪心，对这个数组按照 $$val$$ 值，从高到低进行sort，每次取一个数尝试压入线性基的p数组中，如果成功，将 $$ans$$ 增加 $$val$$ ，最后输出 $$ans$$

正确性：因为线性基的集合大小固定，在固定大小下，贪心选择最大的 $$val$$ 显然是正确的。

数论

Miller-Rabin算法

费马小定理

对于素数 $$p$$ ，存在任意 $$a$$ 满足 $$a$$ , $$p$$ 互质，都有 $a^{(p-1)} \equiv 1 \pmod p$

反过来，如果可以找到一个 $$a$$ ,使得 $a^(p-1)\equiv 1 \pmod p$ 不成立，则 $$p$$ 一定为合数

但注意到，存在一些合数（卡迈克尔数）能通过所以 $$a$$ 的测试，所以仅有这个定理不足以判断 $$p$$ 是否为质数

二次探测定理(Miller's Test)

如果 $$p$$ 是奇素数，那么方程 $x ^ 2 \equiv 1 \pmod p$ 的解只有 $x \equiv 1$ 或 $x \equiv -1$ (即 $$p-1$$ )

基于上述两则定理，我们可以得出Miller-Rabin定理

算法步骤

1. 特判

若 $$n<2$$ 则返回非素数
若 $$n=2$$ 则返回素数
若 $$n$$ 为偶数，返回非素数

2. 分解 $$n-1$$

将 $$n-1$$ 表示为

n-1 = d\times 2^s

其中 $$d$$ 为基数 $s\ge 1$

3.选择底数

选择底数 $$a$$ (可固定或随机)，进行多轮测试

对于每个底数 $$a$$ ，计算

x = a^d \mod n

若 $$x = 1$$ 或者 $$x = n-1$$ 则本轮通过，继续下一个底数

CRT

给定方程

\begin{cases} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ \quad \vdots \\ x \equiv a_n \pmod{m_n}\\ \end{cases}

其中 $$m$$ 互质，求通解 $$x$$

考虑构造 $M = m_1 \times m_2 \times \dots \times m_n$ ， $M_i = {M\over m_i}$

并构造在模 $$M$$ 意义下， $$M_i$$ 的逆元，即 $$t_i$$ 满足

M_i \times t_i \equiv 1 \pmod M

然后构造局部解： $e_i = a_i \times M_i \times t_i$

最后将局部解相加，再对 $$M$$ 取模：

x = \sum ^n _{i=1} e_i \pmod M

这个 $$x$$ 就是在模 $$M$$ 意义下的唯一解。

构造正确性：

以第 $$i$$ 个方程为例：

对于 $e_i = a_i \times M_i \times t_i$ 由于 $$M_i$$ 是其他所有模数的乘积，所以 $M_i\equiv 0 \pmod {m_j}(j \ne i)$ ——所以， $$e_i$$ 对于其他方程贡献为 0 又因为 $M_i \times t_i \equiv 1 \pmod {m_i}$ ，所以 $e_i \equiv a_i \pmod{m_j}$ ——恰好满足第 $$i$$ 个方程

把所有 $$e_i$$ 加起来，每个方程都能被各自对应的那一项满足，而其他项对该方程的贡献就是 0。

答案唯一性：

即，讨论 $$x$$ 为何是模 $$M$$ 意义下唯一解。

证：假设存在两个解 $$x,y$$ ，同时满足 $$n$$ 个同余方程

\begin{cases} x \equiv a_1 \pmod {m_1} ,~~y \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod {m_2} ,~~y \equiv a_2 \pmod{m_2}\\ \quad \vdots \\ x \equiv a_n \pmod {m_n} ,~~y \equiv a_n \pmod{m_n}\\ \end{cases}

显然，对于任意模数 $$m_i$$ ， $$x,y$$ 的差一定被 $$m_i$$ 整除，即

\[m_i | (x-y)\]

这意味着， $$x-y$$ 这个数，同时被 $m_1,m_2,\dots,m_n$ 整除。

又，由CRT前提知， $\gcd (m_i,m_j) = 1(i\ne j)$

又因为如果若干个整数两两互质，且某个数能被它们每一个整除，那么这个数一定能被它们的乘积整除。

即

M | (x-y)\\ 即：\\ x-y \equiv 0 \pmod M \\ x \equiv y

EXCRT

CRT是基于模数互质的前提下的运算，我们考虑进行拓展到一半情况

线性代数

矩阵加速

题目链接

高斯消元

题目链接

模板 线性基

P3857 [TJOI2008] 彩灯

P4570 [BJWC2011] 元素

数论

Miller-Rabin算法

费马小定理

二次探测定理(Miller's Test)

算法步骤

1. 特判

2. 分解 \(n-1\)

3.选择底数

CRT

EXCRT

模板线性基

2. 分解 $\(n-1\)$