线性 die 数

· · 算法·理论

cnblogs

[2025-06-23] 创建文章并加入一些矩阵基本操作。

高斯消元

对于矩阵有 3 个初等变换：

  1. 交换两行
  2. 将一行乘上一个数
  3. 将一行加上另一行的若干倍

若将矩阵的每行看成一个高维向量，上述操作不会改变这些向量的张成。

高斯消元是一种算法可以将一个矩阵通过初等变换变化为只有主对角线上有值（其他为 0）的矩阵而方便处理一些问题。

考虑从上到下确定每个 (i,i) 的值，并使用变换三消除这列的其他值。

考虑如下过程，枚举行 i，若 (i,i) 值为 0 就向下找一行 j 满足 (j,i) 不为 0 并交换两行，然后对除第 i 行之外的所有行加上第 i 行的若干倍使得 \forall j \neq i,a_{j,i} = 0。注意到这样不会影响已经确定值的之前的行，因为第 i 行 i 位置之前全部是 0。

P3389

多元一次方程组是高斯消元解决的经典问题。

考虑一个矩阵，每行依次是第 i 的方程 x_1 \sim x_n 的系数。考虑将这个矩阵变为上述只有主对角线有值的矩阵（操作的时候带上方程右边的数），然后就剩下若干个 ax_i =b 的东西直接算即可。

经典情况是 n 个方程 n 个未知数。若消元过程中出现主对角线上某个值为 0，此时若右边的值为 0，就说明有无数解，否则无解；若未出现如上情况就很简单了。

对于不是 n 个方程依然是先消元，若最后没有消出对角矩阵，根据右边的值是否为 0 来判断无数解或无解，若消出对角矩阵即可直接算出解。

矩阵求逆

若对于矩阵 A 存在矩阵 B 满足 AB = BA = I，则称 B 为 A 的逆，记为 A^{-1}，并称矩阵 A 是可逆的。

首先注意到矩阵的三种初等变换都有对应的矩阵，即对矩阵 A 做初等变换可以看成 A 左乘变换对应的矩阵，对 A 做多次变换就是 A 左乘所有变换依次相乘得到的矩阵（矩阵乘法的结合律）。

由于 A \cdot A^{-1} = I, I \cdot A^{-1} = A^{-1}，考虑对 A 做初等变换使其变为单位矩阵，对单位矩阵做同样的初等变换就变成 A^{-1} 了。若无法消成单位矩阵，就是 A 不可逆。

感觉这个做法非常厉害。

模板题 P4783。

线性基

线性基是一种神秘算法一组基底，可以用至多 \log_2 V 个数表示出一个集合 S 任意子集的异或和。

建立线性基考虑每一位保留一个使得那位为 1 的数，插入的时候从高位向低位考虑，如果当前位为 1，且线性基中还没有代表这位的数，就直接插入，否则异或上线性基中这位的值，去掉待插入数上这位的 1 继续插入。

不难发现这样确实可以表示出任意子集的异或和。

代码如下：

void insert(int x){
    for(int i=51;i>=0;--i) if(x&(1ll<<i)){
        if(!p[i]) return p[i]=x,void();
        x^=p[i];
    }
    return ;
}

也许线性基就是模 2 意义下的高斯消元？

P3812

维护最大异或和是线性基的经典操作。

考虑按位贪心，若当前位为 0 且线性基中此位有值，就异或上。

P3857

直接摆结论，线性基能表示的数的种类数是 2^{|B|}，也就是每个数选或不选。

P4869

线性基能表示出的数有 2^{|B|} 种，且每种数 2^{n-|B|} 个。因为任意一个异或和 （2^n 种选法），在线性基中对应了唯一一种表示方法，并且对于在线性基外的 2^{n-|B|} 中选法加上线性基中的某些数，一定都可以构成某个确定的合法数。

CF1100F

可以 CDQ 分治加线性基合并，这个不需要多说。

还以一种做法，是经典的线性基 trick，前缀线性基，考虑对每个前缀维护线性基，维护能使每一位有值的最靠右的位置 pos。这个可以在之前的基础上插入，预处理是 O(n\log n) 的。

查询 [l,r] 时候，在前缀 r 的线性基中，所有 pos \geq l 的位置是可以使用的。

P4151

考虑异或路径的性质：重复走一个地方两次相当于没有走。

一条路径一定可以通过一条链和一些环表示出来，也就是，随便选一条链，在上面加若干个环可以刻画出所有路径，而且发现无论怎么加环都可以构造出一种合法的走法。

考虑随便选一条链再把所有环扔到线性基里面。

现在的问题是如何找到所有环。考虑建出 dfs 树，对于每条非树边，构成了一个环。如果有环套环的情况，可以发现这样也可以表示出所有可能出现的情况。

梦熊 NOI 第 10 场 T1

相当于选出一些数求异或和，若异或和第 i 位是 1 会产生 3^{b_i} 或 -3^{b_i} 的贡献。

考虑三进制，容易证明 b_i 越大优先级越高。也就是首先将位按照 b_i 降序排序，然后依次检查异或和每一位是否能为 0 (a_i=-1) 或 1 (a_i=1)。容易想到将所有数扔进线性基。

为了方便，下面称异或和某一位为 1 表示这一位取到最优，也就是异或上 [a_i=-1] 之后为 1。

对于 b_i 全都不同的情况，排在前面的数一定比排在后面的优先级高，直接线性基求最大异或和即可。

但是若有两个位 b_i 相同就会出一些问题。设这两个位为 p,p-1，若在最高位至 p-1 的最优策略下，p 和 p-1 都为 1 或都为 0，那么最优策略唯一，没什么不对的。但是若最优策略为两位中有一位为 1，且两位都可以为 1，那么此时出现了两种策略，这可能导致之后的答案不同。

赛时我直接断言这样情况不多，而且注意到贪心部分并非复杂度瓶颈。可以使用随机化，每次随便选一个策略，然后多跑几遍就过掉了这题。但是显然这太蠢了。

考虑这种情况出现的条件。

首先线性基在 p,p-1 两位中应该恰好有一位有值，因为若两位都有值，那么两位都做到了最优，若都没有值，不可能在这出现两种策略。

其次这个值的 p,p-1 位一定都是 1，也就是它必须可以同时影响这两位，那么这个值一定在第 p 位上。

最后到 p 位之前的答案在 这两位上一个是 1，一个是 0，否则线性基第 p 位的值一定可以把两个都变成 1。

考虑到这些限制条件，两种策略的区别实际上就是是否异或线性基的第 p 位，也就是后面需要的时候可以再异或上这个值，直接将它的 p,p-1 位置为 0 然后丢回线性基即可。

梦熊 NOI 第 17 场 T1

结论题，前缀线性基维护。但是场上不会结论所以似了。

一个数能被拆分为两个完全平方数当且仅当所有形如 4k+3 的质数的次数为偶数。

考虑将每个数表示为一个二进制数，每二进制位表示第 i 个如上素数的次数是否为偶数。而原问题就是选出若干个数，异或和为 0 有多少种不同的选法。这是经典的线性基问题。

由于是区间询问，所以使用前缀线性基维护，需要使用树状数组维护在线性基内的下标集合。但是在 10^7 以内形如 4k+3 的质数个数 k 约为 3e5，bitset 维护线性基的插入复杂度是 O(\frac{k^2}{\omega})，再乘上 n 后无法接受。

考虑维护质因数集合的经典套路：根号分治。称 >\sqrt{10^7} 的质数为大质数，其余为小质数。一个数最多含有一个大质因子，考虑只压位维护小质数的集合，再单独存一下每个数的大质因子，插入的时候先考虑大质数再考虑所有小质数即可。10^7 的小质数约为 2e2 个。

行列式求值

cmd 的博客，是下面两小节基础知识部分较为详细的讲解。

一个 n 阶矩阵 A 的行列式 \det(A) = \sum_{P} (-1)^{\mu(P)} \prod_{i=1}^n A_{i,p_i}，其中 P 为排列，\mu(P) 为排列 P 的逆序对数，\det(A) 也可以记为 |A|。

也就是在每行挑一个数（满足每行挑出的数互不相同）乘起来，再根据每行选出的列构成的排列的奇偶性加入答案或从答案中减去这个乘积。

考虑矩阵的三种初等变换对行列式的值的影响。

交换两行

容易发现原本所有排列交换这两个位置后，奇偶性改变，也就是所有排列的系数都取反，那么 \det(A')= -\det(A)。

某一行乘上一个数 k

所有排列奇偶性不变，系数不变。而所有排列对应的乘积都恰有一个数来自这行，所以都乘 k，即 \det(A') = k\det(A)。

某一行加上另一行的 k 倍

这个证明要麻烦一些。首先需要证明两个性质。

性质 1：存在两行相同的矩阵行列式为 0。证明非常巧妙，考虑交换这两行，根据上面的分析行列式应当取反，实际上交换后矩阵没变，那么行列式也不变，只有 0 取反过后还等于自己。

性质 2：对矩阵某一行加上一个向量记为 A'，设原矩阵为 A，将 A 那行替换为这个向量，剩余部分不变的矩阵为 B，则 \det(A') = \det(A) + \det(B)。证明考虑乘法分配律，将那行原来的部分和新加的部分拆开即可。

那么对于第三种初等变换，即对于 A 的第 i 行将其变为 A_{i,k} = A_{i,k} + t A_{j,k}。设矩阵 B 第 i 行为 tA_j 其余与 A 相同，对 B 的第 i 行乘上 t^{-1} 得到 B'，则 \det(B)= t^{-1} \det(B')，而根据性质 2 \det(B') =0，所以 \det(B) =0。

而根据性质 1，\det(A') = \det(A) + \det(B) = \det(A)，所以，第三种初等变换不改变行列式。

那么如何求一个矩阵的行列式？注意到上三角矩阵只存在一种在每行选数的方案（即第 i 行选第 i 个）满足所有选出的数都非 0，且这种选法系数为 1，所以上三角矩阵的行列式为对角线乘积。

考虑通过三种初等变换将矩阵消为上三角矩阵，实际上用不到变换二。注意到剩下的只有变换一会影响行列式的值，只需记录进行交换的次数来确定答案要乘上多少个 -1 即可。

模板题 P7112。

Matrix-Tree 定理

不会线性代数，不会证明，直接摆结论了。

设 A 为邻接矩阵，D 为度数矩阵（D_{i,i} 为结点 i 的度数，其它位置是 0），K=D-A，K' 为 K 去掉任意第 k 行第 k 列的矩阵，\det(K') 即为生成树个数。

P4111

容易发现题目就是在相邻的空格子之间连边建图，求生成树个数。建完图按照上述方法求下生成树个数即可。

模数不是质数，神秘。消元似乎得用辗转相除。

P3317

矩阵树定理加权扩展。

实际上这个行列式的结果是所有边权的乘积，由于不带权图邻接矩阵相当于默认边权为 1，所以每棵生成树的权值是 1，最终答案就是生成树个数。

还有一种理解方式，若存在重边，有那条边的生成树个数会乘上重边个数，所以一种形态的树被算的次数是每条边的重边个数的乘积。边权可以理解为重边个数。

令一棵树的权值为所有边权的乘积，而要求所有生成树的边权和，就把原来的邻接矩阵每一个位置改为连接那两点的边权和，度数矩阵改为与当前点相连的边的权值和。

本题中，令一棵生成树的权值为 \prod_{(i,j)\in E_T} G_{i,j} \prod_{(i,j)\notin E_T} (1-G_{i,j}) (i<j)，题目要求的就是所有生成树的权值和。但是这涉及到树外的东西，不好直接算。

稍微化一下，可以写为，\prod_{(i,j)\in E_T} \frac{G_{i,j}}{1-G_{i,j}} \prod_{(i,j)} (1-G_{i,j}) (i<j)，后面的东西提出来一起乘，只用求出前面东西的和即可。用矩阵树加权扩展就可以求。

P6178

对于第一问，直接把邻接矩阵和度数矩阵改为边权和矩阵算行列式。

对于有向图，矩阵树定理也是能用的。对于内向树，D_{i,i}=\sum_{i=1}^n A_{i,j}，即出该点的边权总和；对于外向树，D_{i,i}=\sum_{i=1}^n A_{j,i}，即入该点的边权和。（与直观感觉是相反的，很奇怪啊）

第二问求外向树，按照上述方法改一下度数矩阵就行。

P4033

考虑到这种图每个点出度都是 1，最后只会形成若干基环树。由于题目要求从任意一点出发都能出去，所以不能存在环，也就是只能是一片森林。

把现有的图连出来，若已经出现环，答案显然是 0。剩下一片森林，每棵树的根要么是 . 点，还未确定出边，要么是连向花园外的点。

现在要做的是把以 . 为根的树接到别的树上去，使得最终的图是森林。发现目前树的形态并没有影响，可以把当前每棵树抽象成一个大点，大点之间连边，可以发现最后形成的是大点构成的森林。

但是森林并不好算方案。发现森林每棵树的根都连向花园外，可以新建一个代表外面的虚点把这些点合为一个大点。然后就可以用矩阵树定理算方案了。

P4336

思路很简单也很自然，为什么我当时没有想到！

题目要求生成树的方案数，显然是矩阵树定理。要求每条边分配给一个公司这个限制导致我们不能直接使用。

注意到公司很少。考虑容斥，只需要对于每个公司集合算方案数。做完了。

P6624

本题通过一些数论，容斥相关转化，只需要解决求所有生成树的边权和这个问题。

矩阵树定理求出的答案是所有生成树边权积的和，实际上边权不仅仅限于一个数，它也可以是别的东西，比如多项式。

考虑边权和如何转化为边权积：依次枚举一棵树的每条边，这条边算边权 w，其它边算 1，乘起来再求和，也就是将每条边边权看为 wx+1，求边权乘积的 x 项系数。

对于矩阵的每个位置维护一个多项式即可。由于最终求一次项，所以计算过程中只需要保留一次项和常数项。

涉及到多（二）项式乘法和求逆，使用多项式科技或手推均可。

BEST 定理

称一个图是欧拉图，当且仅当所有非零度点强连通，且每个点的入度等于出度，记点 i 的入度或出度为 deg_i。

欧拉图欧拉回路的个数 = 外向树的个数 \times \prod (deg_i-1)!。

证明可以考虑构造双射，我不会，可以阅读 OI-Wiki。

外向树个数用矩阵树定理求即可。

P5807

模板题，知道定理后难点在于欧拉图的判定。

注意到题目的是从 1 出发的路径方案数，对于一个欧拉回路，从 1 出发有 deg_1 种走法，所以答案还要乘上 deg_1。

test #11 有非常多 corner case.

梦熊 NOI 第 19 场 T2

可以将问题转化为：3 个点，9 种边，每个矩阵视为一个有向图，图内每种边各有若干条。按照排列 P 的顺序在每个矩形中选一条边，要求构成从 1 出发回到 1 的回路。

考虑将确定排列计数选法改为确定选法计数排列，也就是先选边，再计算在这个选边方案下有多少条从 1 出发的欧拉回路。

使用 BEST 定理，需要同时算外向树，度数积，和判断欧拉回路。

度数积和判定欧拉回路都与度数有关，记录 1,2 点的入度出度即可，3 点度数可以通过已知信息计算。

外向树直接压 6 种本质不同的状态转移，需要讨论每种状态加边之后是/否将这条边加入外向树会转移到什么状态，细节较多。

注意若存在与 1 不连通的孤点也是合法的，需要对每种情况单独计算。