307 uoj#698. 【候选队互测2022】枪打出头鸟
异或卷积算法的本质：考察 \([x^u]F\) 与 \([x^v]G\) 贡献到 \([x^w]H\) 的本质，其贡献系数为 \((-1)^{u\cdot w}(-1)^{v\cdot w}=(-1)^{(u+v)\cdot w}\)，恰好为 \(u+v\) 对应的 FWT 系数。
求正交线性基：先将线性基三角化得到 \(k\) 个关键位，直接将线性基除主对角线的部分转置，并令正交线性基剩下的 \(n-k\) 个位为关键位，复杂度 \(O(n^2)\)。
\([x^w]\hat A=2^k\) 的 \(w\) 构成了正交线性基的张成空间。
线性基求交：\(A\cap B=(A^{\perp}+B^{\perp})^{\perp}\)（\(A^{\perp}\) 表示 \(A\) 的正交线性基），复杂度 \(O(n^2)\)。
于是这题做法就是，倒着扫描序列做线性基求交，尝试用类似 前缀线性基 的方法记录每个基底最靠前的出现位置，询问直接在正交线性基里搞搞就好了（大概吧）？
308 CF1523H Hopping Around the Array
广告：他是 ISIJ 第一名，也是在线知名题库的洛谷“网红” 。
之前讲过，不过早就不记得了。
一个点进行若干次操作后到达的一定是一个区间，于是想到倍增求出多少步才能跨越过 \(r\)，设出 \(f_{i,j,k}\) 表示从 \(i\) 出发跳 \(2^j\) 步，删除 \(k\) 个点能到的最远位置，预处理其需要用 ST 表处理区间最值，这里的复杂度是 \(O(nk^2\log n+nk\log^2 n)\)。
考虑如何处理查询，令 \(g_i\) 表示删了 \(i\) 个点，我们至多能跳多少步使得不越过 \(r\)，转移就从高到低枚举每一位考虑每个 \(g_i\) 能否塞一个 \(2^k\) 进去。
这样做空间是 \(O(nk\log^2 n)\) 的，离线做就可以做到 \(O(nk\log n)\) 的空间。
309 CF1616G Just Add an Edge
首先判掉初始就有一条哈密顿路的情况，手玩可知我们要找到两条链，构成全集的二划分。
更精准的刻画是（假设加入的边是 \(x\leftarrow y\)）：\(1\rightarrow y-1\rightarrow x\rightarrow y\rightarrow x+1\rightarrow n\)（其中 \(1\rightarrow y-1,x+1\rightarrow n\) 均只使用 \((z,z+1)\) 类边）。
不会做啊啊。
由于不存在哈密顿路，一定存在一个 \((z,z+1)\not\in E\)，因此这两个位置分别属于两条链，容易得知选择连边的两个点 \(x\leftarrow y\) 一定满足 \(x-1\leqslant z\leqslant y\)。
所有这样的 \((z,z+1),(z+1,z)\) 都必须经过，我们可以从前往后 dp 一下就好了，复杂度 \(O(n+m)\)。