早就退役啦!
乍一看挺水的。
P2455 [SDOI2006]线性方程组
板子题。
P4035 [JSOI2008]球形空间产生器
给定一个 \(n\) 维的球体上 \(n+1\) 个点的坐标 \(a_{i,j}\)。求球心坐标 \(\left(x_1,x_2,\ldots,x_n\right)\)。
球心到所有点距离相等,那么只需要 \(\forall{i\in\left[1,n+1\right]}:\sum_{j=1}^n\left(a_{i,j}-x_j\right)^2=C\),\(C\) 为常数即可。
但是,这是 \(n+1\) 个 \(n\) 元二次方程啊。怎么办?我们相邻做差,就成了 \(n\) 个 \(n\) 元一次方程。
具体地 \(\sum_{j=1}^n\left(\left(a_{i,j}-x_j\right)^2-\left(a_{i+1,j}-x_j\right)^2\right)=\sum_{j=1}^n{a_{i,j}^2-a_{i+1,j}^2-2\left(a_{i,j}-a_{i+1,j}\right)x_j}=0\),即 \(\sum_{j=1}^n2\left(a_{i,j}-a_{i+1,j}\right)x_j=\sum_{j=1}^na_{i,j}^2-a_{i+1,j}^2\)。
为了更清晰,写出它的增广矩阵:
\[\begin{bmatrix}2\left(a_{1,1}-a_{2,1}\right)&2\left(a_{1,2}-a_{2,2}\right)&\cdots&2\left(a_{1,n}-a_{2,n}\right)&\sum\limits_{j=0}^n\left(a_{1,j}^2-a_{2,j}^2\right)\\\vdots&\vdots&\ddots&\vdots&\vdots\\2\left(a_{n,1}-a_{n+1,2}\right)&2\left(a_{n,2}-a_{n+1,2}\right)&\cdots&2\left(a_{n,n}-a_{n+1,n}\right)&\sum\limits_{j=0}^n\left(a_{n,j}^2-a_{n+1,j}^2\right)\end{bmatrix} \]Gauss 消元就完事了。
P2447 [SDOI2010] 外星千足虫
\(\bmod{2}/\operatorname{XOR}\) 意义下的高斯消元。
用 bitset<>
搞,复杂度是 \(\mathcal{O}\left(\dfrac{n^2m}{w}\right)\)。