WC 记录

P1224：给定 \(n\) 个 \(d\) 维向量 \(A_i\)，判断存在 \(i,j\) 使得 \(A_i\) 与 \(A_j\) 的内积为 \(k\) 的倍数，构造方案。\(n\le 10^5,d\le 30,k\in\{2,3\}\)。

题解：考虑 \(k=2\) 的情形。构造矩阵 \(M=A_1|A_2|...|A_k\)，\(E=M\cdot M^T\) 那么 \(A_i\) 与 \(A_j\) 的内积等于 \(E_{i,j}\)。尝试判断模 \(2\) 意义下 \(E\) 是否为全 \(1\) 矩阵 \(X\)。随机一个 \(n\times 1\) 矩阵 \(r\)，判断 \(r\cdots M\cdots M^T\) 是否等于 \(X\cdots r\)。这是容易计算的，复杂度为 \(O(Tnd)\)，多跑几次正确率很高，构造方案是简单的。对于 \(k=3\)，注意到 \(1^2=2^2=1\mod 3\)，所以等价于矩阵 \(F_{i,j}=\sum (A_{i,x}\times A_{j,x})^2=\sum\limits_{x,y} A_{i,x}\times A_{j,x}\times A_{i,y}\times A_{j,y}\) 模 \(3\) 意义下是否全为一。\(F\) 可以视作一个 \((d^2)\times n\) 的矩阵与其转置矩阵相乘，后续做法同上，复杂度 \(O(Tnd^2)\)。

zky 原创题：给定序列 \(A\)，要求支持区间 \(\text{reverse}\)，区间查询选取区间内元素子集得到的最大 \(\text{xor}\) 和。\(n,q\le 5\times 10^4,A_i\le 2^60\)。

题解：考虑随机 \(K\) 个序列 \(B\)，\(B_i\) 有一半概率为 \(A_i\)，一般概率为 \(0\)。可以用平衡树维护这 \(K\) 个序列。有以下结论：对于询问 \([l,r]\)，取 \(K\) 个序列中 \([l,r]\) 的异或和构成的线性基仅有 \(\frac{1}{2^K}\) 的概率与 \(A_i\) 中 \([l,r]\) 内元素线性基不等。感性理解就是，该线性基一定是真正线性基的子空间。随机 \(K\) 个元素得到 \(2^K\) 种线性组合，大概率得到真正的线性基。复杂度 \(n\log(nV)^2\)。

一般图最大匹配。\(n\le 500\)。

QOJ8830：给定 $