线性代数

Lcm_simida · 2026-03-04 16:58:10 · 算法·理论

~~敢相信这是一天的学习内容（虽然补了一周）~~

线性代数

线性基

对于一个序列，构造一个最小子集，使得序列中的每个数都可以通过子集中的任意数异或得来,下文以 \oplus 表示异或。
性质：
1. 序列中的每个数都可以通过子集中的任意数异或得来（就是定义）。
2. 子集中的数异或起来不会等于 0（易证，考虑反证法，如果 \oplus_{i=1}^{num}{a_i}=0 了，那么 (\oplus_{i=1}^{k-1}{a_i}) \oplus (\oplus_{i=k+1}^{num}{a_i})=a_{k}，则可以删去 a 中任意值，显然不满足是最小的）。
3. 个数唯一且最少（感性理解下）。
实现：因为异或，考虑按位实现，由 x=\sum a_i\times 2^i，可以通过异或使得某一位为空，考虑高斯消元。每一个数字从高位到低位维护，记录 h_i 表示二进制下最高位为 i 的且通过异或得来的数，对于插入的数消掉高位即可。
作用：求出子序列异或的第 k 值，因为可组成的数的数量只有 2^{num} 个。以及各类原理扩展人类智慧。

code：

struct Hamel{
long long h[MN+1]={0},num=0;
void insert(long long x){
    if(x) for(int i=MN;i>=0;i--) if(x>>i&1){
        if(h[i]) x^=h[i];
        else{h[i]=x,num++;break;}
    }
}
long long maxx(long long ans=0){for(int i=MN;i>=0;i--) ans=max(ans,ans^h[i]);return ans;}
long long minn(long long ans=0){for(int i=MN;i>=0;i--) ans=min(ans,ans^h[i]);return ans;}
long long query(long long k){
    long long ans=0,nm=num;for(int i=MN;i>=0;i--) if(h[i])
        nm--,ans=((ans)>>i&1?ans^h[i]:ans),(k<=(1ll<<nm)?(ans^=h[i]):(k-=(1ll<<nm)));
    return ans;
}
}hamel;

P3265 [JLOI2015] 装备购买

题意：有 n 件物品，每件物品有价格和 m 个属性，用向量 \mathbf{z_i} 表示，如果买了 \mathbf{z_{c_1}}, \ldots , \mathbf{z_{c_p}}这 p 件装备，那么对于任意待决定的 \mathbf{z_h}，不存在实数序列 b_1, \ldots ,b_p使得 b_1\mathbf{z_{i_1}} + \ldots + b_p\mathbf{z_{i_p}} = \mathbf{z_h}，那么脸哥就会买，否则不买。问最多买的物品数和最少价格，n,m\le 500。
注意到该向量可以满足加减乘除运算，数据还小，考虑使用 \color{blue}{类线性基的高斯消元} 解决。
P4301 [CQOI2013] 新Nim游戏
题意：有 n 堆石子，每堆 a_i 个，先手和后手拿走任意堆，再由先手开始做Nim博弈，问先手必胜最少拿几个石子。
由Nim博弈转化为求 \sum{a_{b_i}} 的最小值使得后手不能构造出异或值为 0 的序列，便是线性基裸题。
因为石子要最少，则考虑从大到小排序，因为这样大的数先被插入，小的数才会被拿走。
CF1100F Ivan and Burgers
题意：给定序列 a，问区间 [l,r] 的异或最大值，不要求在线。
考虑离线，再用线性基，问题是如何在 [1,r] 的区间里查 \ge j 的值里面的最大异或值。
发现位置越后越有可能被用，所以记录下高斯消元里的位置，再针对令位置值最大。

code：

struct Hamel{
int h[MN+1]={0},pos[MN+1],num=0;
void insert(int x,int id){
    if(x) for(int i=MN;i>=0;i--) if(x>>i&1){
        if(h[i]){if(pos[i]<id) swap(x,h[i]),swap(id,pos[i]);x^=h[i];}
        else{h[i]=x,pos[i]=id,num++;break;}
    }
}
long long maxx(int cnt){long long ans=0;for(int i=MN;i>=0;i--) if(pos[i]>=cnt) ans=max(ans,ans^h[i]);return ans;}
}hamel;

CF587E Duff as a Queen

题意：有长度为 n 的序列，有两种操作：1.区间异或。2.查询区间中最多能异或出几个数。
解析：看到 \color{blue}{区间异或}，想到差分，令 b_i=a_i\oplus a_{i-1}，则修改只要改两个位置。
异或出几个数也就是 2^{线性基中数的个数}，考虑线段树维护 b 数组的区间线性基，时间 O(qlog^3V)，树状数组维护查询 a_l 的值。
P4151 [WC2011] 最大XOR和路径
题意：n 个点的图，每条边有边权，问 1 到 n 到最大异或路径。
神秘图论性质：注意到答案一定是一条 1 到 n 到路径再异或上很多环组成的。
因为可以通过环来不断增广该路径。之后就把环存进线性基即可。
### [P11620 [Ynoi Easy Round 2025] TEST_34](https://www.luogu.com.cn/problem/P11620)
题意：长度为 n 的序列，两种操作：1.区间异或。2.在 [l,r] 中，找到一个异或值使其异或 v 最大。
做法1:差分，再通过线段树维护区间线性基，树状数组维护 a_l 的值，\color{blue}{每次查询加入b_{l+1},\ldots,b_r和a_l的值}。
做法2:\color{blue}{Zak神秘做法}，每次随机选出 log (r-l+1) 个子集，再加入线性基。
Even Circuit
题意：求最小的偶数长度的子集异或和为 0 的长度，n\le 2\times 10^5,a_i\le 2^{22}。
抽象诈骗题（人被诈骗傻了）。
考虑到题目可以转化成求两个不同但长度均为 k 的子集，那么答案就是最小的 2k，因为如果相交了一定不是最优的。
若 \binom{n}{k}>2^{22}，那么答案一定小于 2k，对于另一部分很好搞。
Gemcrate
题意：有 n 个宝石，对于宝石分组，组内的权值为组内宝石权值异或和，答案为每组权值的按位与，求最大的答案。
如果最终分组个数为奇数，那么最后答案一定不优于分 1 组的情况。
如果最终分组个数为偶数，那么最后答案一定不优于剩下一组，其他分在一起的情况，也就是分 2 组。
所以我们暂且得出结论：最终答案分为 1 组或 2 组。
对于 1 组的情况很好搞，对于 2 组情况，因为 \color{blue}{只有出现次数为偶数的位置可以产生贡献}，所以把出现次数为奇数的位置删去，那么 \color{blue}{所有值的异或和为0}，这变成了线性基模版。
行列式
这里只讲实现。

对于一个 n\times n 的矩阵 A（n 阶方阵），其 n 阶行列式写作 \det(A) 或者 |A|，定义为：
\det(A)=|A|=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n a_{i,p_i}
当然，~~上述的东西用不上~~，只需要知道以下性质：
- 矩阵转置，行列式不变；
- 矩阵行（列）交换，行列式 \color{blue}{取反}；
- 矩阵行（列）相加或相减，行列式不变；
- 矩阵行（列）所有元素同时乘以数 k，行列式等比例变大。
- 当矩阵只有主对角线有值时 \det(A) 就是对角线相乘。
由上便可以发现可以使用高斯消元算 \det(A)。

Code：

struct Determ{
long long a[N][N];
long long del(){
    long long ans=1,w=1,cc;for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){
        while(a[i][i]){cc=a[j][i]/a[i][i];for(int k=1;k<=n;k++) a[j][k]=((a[j][k]-cc*a[i][k]%P)%P+P)%P;swap(a[i],a[j]),w=-w;}
        swap(a[i],a[j]),w=-w;
    }for(int i=1;i<=n;i++) ans=ans*a[i][i]%P;return (ans*w%P+P)%P;
}
}cnt;

LGV 引理

先看几个超绝弱化版：
- 引子1：有一个人从 (1,1) 走到 (n,n)，经过的点只能到中轴线下方，问方案数。
- 解法1：显然从 (1,1) 走到 (n,n) 到方案数为 \binom{2n-2}{n-1}，将每条路径第一次经过直线 y=x+1 的点到 (n,n) 到路径按该直线对称，发现此时会到达 (n-1,n+1)，并且与每条不合法路线一一映射，其实这就是卡特兰数，答案即 \binom{2n-2}{n-1}-\binom{2n-2}{n-2}。
- 引子2：有两个人从 (1,1) 走到 (m,n)，两条路径不能相交，问方案数。
- 解法2：因为不相交，那么第一步一定确定，分别到达 (1,2),(2,1)，最后分别到达 (n-1,n),(n,n-1)，，还是考虑容斥，将两个人第一次相交的点之后两个人的路径交换，之后发现路径为 \binom{m+n-3}{n-1}\times\binom{n+m-3}{m-1}，且与不合法方案一一对应。
LGV 引理告诉我们：对于一个 \color{blue}{有向无环图}，若有 n 个起点，n 个终点，令 e(i,j) 表示第 i 个起点到第 j 个终点的方案数，A=\begin{bmatrix} e(1,1) & e(1,2)\ldots e(1,n)\\ e(2,1) & e(2,2)\ldots e(2,n)\\ \ldots \\ e(n,1) & e(n,1)\ldots e(n,n) \end{bmatrix}，那么所有第 i 个起点到第 i 个终点且路径不相交的方案数是 \det(A)。
模版：P6657 【模板】LGV 引理
CF348D Turtles
题意：有两个人从 (1,1) 走到 (m,n)，两条路径不能相交，有几个点不能走，问方案数，n,m\le 3000。
解析：直接dp即可。
Monotonic Matrix：
题意：给定 n,m，构造一个 n\times m 的矩阵，需要满足 a_{i-1,j}\le a_{i,j},a_{i,j-1}\le a_{i,j},0\le a_{i,j}\le 2，问方案数。
转化为求分界线即可，其中分界线不可相交（其实可以把 \le 2 改为 \le k）。
矩阵树定理
建议看这里，很详细，注意 \color{blue}{根} 的细节即可（又是考验记忆力的一环）。
例题：
模版：P6178 【模板】Matrix-Tree 定理&P4111 [HEOI2015] 小 Z 的房间&P4455 [CQOI2018] 社交网络
P4336 [SHOI2016] 黑暗前的幻想乡
题意：给出 n-1 个边集，求从每个边集中选一条边构成生成树的方案数，n\le 17。

有点神秘，考虑容斥，可以用矩阵树定理算 f_S 表示选了 S 这个边集构成的方案数，最后用答案即为有偶数个边集没选-有奇数个边集没选。

struct Determ{
long long a[N][N],n;
int del(){
    long long ans=1,w=1,cc;for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){
        while(a[i][i]){cc=a[j][i]/a[i][i];for(int k=1;k<=n;k++) a[j][k]=((a[j][k]-cc*a[i][k]%P)%P+P)%P;swap(a[i],a[j]),w=-w;}
        swap(a[i],a[j]),w=-w;
    }for(int i=1;i<=n;i++) ans=ans*a[i][i]%P;return (ans*w%P+P)%P;
}int count_tree(){
    long long ans=1,w=1,cc;for(int i=2;i<=n;i++) for(int j=i+1;j<=n;j++){
        while(a[i][i]){cc=a[j][i]/a[i][i];for(int k=1;k<=n;k++) a[j][k]=((a[j][k]-cc*a[i][k]%P)%P+P)%P;swap(a[i],a[j]),w=-w;}
        swap(a[i],a[j]),w=-w;
    }for(int i=2;i<=n;i++) ans=ans*a[i][i]%P;return (ans*w%P+P)%P;
}void add(int x,int y,int w,int flag){
    (flag?(a[x][y]=(a[x][y]-w+P)%P,a[y][y]=(a[y][y]+w)%P):/*外向*/
    (a[x][y]=(a[x][y]-w+P)%P,a[y][x]=(a[y][x]-w+P)%P,a[x][x]=(a[x][x]+w)%P,a[y][y]=(a[y][y]+w)%P));
}
}cnt;

P3317 [SDOI2014] 重建

题意：给出每条边出现的概率，问成为生成树的概率。
发现答案为每条生成树概率之和。
还有一个问题：\color{blue}{其他边不出现的概率还要考虑}。可以先把每条边的边权改为 \frac{a_{i,j}}{1-a_{i,j}}，最后答案对于每条边再乘以 1-a_{i,j} 即可。
注意若 a_{i,j}=1，那么可以将其剪去无穷小。
AT_jsc2021_g Spanning Tree
题意：给出每条边是必须选、必须不选、可选可不选中的哪一个，问是生成树的方案数，n\le 300。
解析：发现只需特殊考虑必须选的边，那么就是新选的边不可以使必选的边成为环，用并查集维护哪些点已经是一个联通块即可。
AT_abc253_h [ABC253Ex] We Love Forest
题意：有 m 条边，对于 k\in[1,m-1] 求出随机选 k 条边不构成环的概率，n\le 14。
转化为求方案数再除以 m^i。
发现若 k\ge n 则无解，那么对于 k<n 的情况直接枚举联通块的点即可。
~~但是貌似要用集合幂集数，不然直接时间爆炸~~。
P2144 [FJOI2007] 轮状病毒
最后给几道黑紫困难题
AT_abc323_g [ABC323G] Inversion of Tree
P2144 [FJOI2007] 轮状病毒
P6624 [省选联考 2020 A 卷] 作业题
P5296 [北京省选集训2019] 生成树计数

线性代数

线性代数

线性基

P3265 [JLOI2015] 装备购买

P4301 [CQOI2013] 新Nim游戏

CF1100F Ivan and Burgers

CF587E Duff as a Queen

P4151 [WC2011] 最大XOR和路径

Even Circuit

Gemcrate

行列式

LGV 引理

CF348D Turtles

Monotonic Matrix：

矩阵树定理

P4336 [SHOI2016] 黑暗前的幻想乡

P3317 [SDOI2014] 重建

AT_jsc2021_g Spanning Tree

AT_abc253_h [ABC253Ex] We Love Forest

最后给几道黑紫困难题