线性代数 #

高斯消元法 #

LG P4035 [JSOI2008] 球形空间产生器 #

给定 $n$ 维空间中的 $n + 1$ 个点，求通过这几个点的 $n$ 维球的球心，数据保证一定存在解 $1 \leq n \leq 10$

• 列出方程组求解即可，其实就是 $n$ 个 $n - 1$ 维流形的交

LG P5027 Barracuda #

给定 $n$ 元的 $n + 1$ 个方程的线性方程组(特殊的还有系数均为0或1，常数项为正整数)，其中恰有一个方程是错误的，在满足所有解都是正整数且最大元唯一的条件下，若可能的错误的方程有多个，输出不合法，否则输出最大元 $1 \leq n \leq 100$

• 可以跑 $n$ 次高斯消元实现 $O(n^4)$
• 注意系数均为0或1，常数项为正整数的方程组唯一解时，解可以不是整数（被这个坑了）

hdu5833 [2016CCPC网络赛] Zhu and 772002 #

给定 $n$ 个正整数 $a_i$，现在可以选择若干数字相乘，问得到的结果是完全平方数的方案数有多少种，限制给定数字的所有质因子不超过 $2000$ $1 \leq n \leq 300, 1 \leq a_i \leq 10^{18}$

• 值域很大但是 $n$ 和质数个数较少，可以考虑转化为解关于质数指数的异或方程组，最后的方案数其实就是自由元集合的全体非空子集的个数，也等价于求矩阵的秩(即主元个数)

LG P2962 [USACO09NOV] Lights G #

给定一张由若干电线连接的灯泡网络，形成一个 $n$ 个顶点，$m$ 条边的无向图，每个顶点有一个灯泡和一个开关，初始时灯泡都是熄灭，打开一个开关会改变对应的灯和与这个顶点直接相连的顶点对于的灯的状态，问最少需要开多少次开关能使得灯全部点亮 $1 \leq n \leq 35, 1 \leq m \leq 595$

• 求解异或方程组确定主元和自由元，对自由元进行二进制枚举的dfs，需要剪枝剪掉已经大于当前最小值的枝才能通过
• 一个复杂度更严谨的做法其实可以直接折半搜索，理论复杂度也正确

LG P2447 [SDOI2010] 外星千足虫 #

给定 $m$ 个 $n$ 元异或(原题是模2下判奇偶)方程组，问前多少个方程可以完全确定所有未知数的奇偶性，并输出每个数的奇偶性或判断为不可确定，题目保证不会无解 $1 \leq n \leq 1000, 1 \leq m \leq 2000$

• 在跑异或高斯消元每次选取这一列的 $1$ 时取序号最小的方程组，并维护每次选取中的最大值即可
• 理论上 $O(n^2m)$ 应该会超时的，可以使用 bitset 优化到 $O(\frac{n^2m}{w})$，但不知道为什么过了，只跑了300ms

hdu5755 [2016hdu多校3] Gambler Bo #

给定一个 $n \times m$ 的网格，初始时每个网格都有一个值，值为小于 $3$ 的正整数，每一次操作可以选定一个格子，使得该格子数字加 $2$，它四周的格子(没有超边界下)加 $1$，所有加法都在模 $3$ 意义下进行，请构造一种方案使得所有格子变为 $0$ $1 \leq T \leq 10$ 组测试，$1 \leq n, m \leq 30$

• 模3下的电灯问题，强行进行解同余方程组，时间复杂度 $O(Tn^3m^3)$ 理论上是超时的，但卡常(避免掉模3)过了
• 据说有 $O(Tm^3)$ 的做法