官方题解只能做到 $O(n \log^2 V)$？玩的太差了。令 $b=32 = O(\log V)$。这道题可以做到 $O(nb)$ 时间、$O(nb)$ 空间，不需要对每个候选空间分别进行高斯消元，也不需要比较排序。算法的随机性仅用于最终去重，碰撞概率可以严格控制在极低水平。

题目要求统计所有非空区间张成的不同 $\mathbb F_2$ 子空间，输入满足 $0\le a_i < 2^{32}$，所有测试的长度之和不超过 $10^5$。([QOJ][1])

固定右端点，从右往左加入元素，张成空间只会扩大，每次严格扩大都会使维度增加。因此，每个右端点至多对应 $b$ 个不同的正维子空间。常规做法枚举这些空间，再维护规范线性基及其哈希，容易得到 $O(nb^2)$ 的复杂度。要消掉剩下的一个 $b$，关键是：不要分别维护这些空间，而是用一种支持整体更新的表示，维护整条空间链。

子空间可以用一条多项式复合链表示

选择域 $K=\mathbb F_{2^{128}}$，把输入的 $32$ 个二进制位嵌入其多项式基的低 $32$ 位。这个映射是 $\mathbb F_2$ 线性的单射，因此完全保留异或关系和线性相关性。以下加法、乘法和平方都在 $K$ 中进行，其中加法就是异或。

对于子空间 $S$，定义它的子空间多项式 $P_S(X)=\prod_{s\in S}(X+s)$。这个多项式只由 $S$ 决定，其根集恰好是 $S$，所以不同子空间对应不同多项式。

看起来它的次数可能高达 $2^{32}$，但我们不会展开它。

首先，$P_{{0}}(X)=X$。假设 $v\notin S$，令 $T=S+\langle v\rangle$，那么 $T$ 是 $S$ 与 $v+S$ 的不交并。如果 $P_S$ 满足可加性，就有

$$ P_T(X)=P_S(X)P_S(X+v) =P_S(X)^2+P_S(v)P_S(X). $$

这个式子又保持可加性：在特征为 $2$ 的域中，$(u+v)^2=u^2+v^2$。从 $P_{{0}}(X)=X$ 开始归纳，便证明了所有子空间多项式都满足 $P_S(u+v)=P_S(u)+P_S(v)$，而且只包含次数为 $2$ 的幂的项。

记 $L_c(X)=X^2+cX$。上面的结论就是：向 $S$ 加入一个独立向量 $v$ 时，新的子空间多项式为 $L_{P_S(v)}\circ P_S$。

现在考虑某个右端点对应的后缀空间。去掉重复空间，并补上辅助空间 ${0}$，可以写成链 $U_0={0}\subset U_1\subset\cdots\subset U_d$，其中 $\dim U_i=i$。

每一层都存在一个非零域元素 $c_i$，使得 $P_{U_i}=L_{c_i}\circ P_{U_{i-1}}$。于是，整条空间链只需要保存 $c_1,c_2,\ldots,c_d$ 这 $d$ 个域元素。

具体地，任选 $v_i\in U_i\setminus U_{i-1}$，都有 $c_i=P_{U_{i-1}}(v_i)$。由于同一陪集里的向量相差一个 $U_{i-1}$ 中的元素，选择哪个 $v_i$ 都不会改变这个值。实现时不需要保存这些 $v_i$，它们只用于证明。

再固定一个随机点 $z\in K$。从 $h_0=z$ 开始，依次计算 $h_i=h_{i-1}^2+c_i h_{i-1}$，就得到了 $h_i=P_{U_i}(z)$。因此，整条链的所有子空间指纹同样只需要 $O(d)$ 次域运算。

注意，这里计算的是子空间多项式在固定点的值，不是对 $c_1,\ldots,c_i$ 做普通滚动哈希。不同的空间链可能用不同的复合系数表示同一个最终空间，但最终得到的 $P_S(z)$ 一定相同。

追加一个数，如何在线性时间内更新整条链

设旧链为 $U_0,\ldots,U_d$，现在在序列末尾追加非零向量 $x$。

新后缀空间正是 $W_i=U_i+\langle x\rangle$，其中 $0\le i\le d$，再去掉重复项。我们要从旧系数 $c_i$ 直接计算新系数，不能重新构造每个 $W_i$。

令 $y_i=P_{U_i}(x)$，初始 $y_0=x$。由旧链的递推式，依次计算 $y_i=y_{i-1}^2+c_i y_{i-1}$，便能在一次扫描中得到这些值。

这里有一个重要性质：$y_i=0$ 当且仅当 $x\in U_i$，这是精确判断，不是哈希判断。 因为 $P_{U_i}$ 的根集恰好就是 $U_i$。

设 $k$ 是第一个满足 $y_k=0$ 的位置。如果不存在，就令 $k=d+1$。

在 $i

$$ c'_{i+1}=c_i(c_i+y_{i-1}), \qquad y_i=y_{i-1}(c_i+y_{i-1}). $$

新链的第一个系数显然是 $c'_1=x$，因为它的第一个空间是 $\langle x\rangle$。随后，每处理一个旧系数，就能用常数次域运算产生一个新系数。

实现时还可以共用乘积 $p=c_i y_{i-1}$，分别计算 $c'*{i+1}=c_i^2+p$ 和 $y_i=y*{i-1}^2+p$。这样，每一步只需要一次域乘法和两次平方。

如果扫描到了 $k\le d$，由于此前 $y_{k-1}\ne0$，等式 $y_k=y_{k-1}(c_k+y_{k-1})=0$ 等价于 $c_k=y_{k-1}$。此时产生的新系数为零，意味着这一层没有发生维度增长。

为什么可以直接停下来？因为 $x\in U_k\setminus U_{k-1}$，所以 $W_{k-1}=U_k$；同时，对所有 $i\ge k$，都有 $W_i=U_i$。也就是说，新链在第 $k$ 维重新接上了旧链，后面完全不变。

因此，更新过程非常简单：先放入新系数 $x$，依次使用上式生成后续系数；一旦遇到 $c_i=y_{i-1}$，就跳过这个零系数，并保留旧数组中第 $i+1$ 项及之后的部分。若始终没有遇到，则链长增加一。

不能把零系数保留下来。 零系数对应的是 $P\mapsto P^2$，它会增加根的重数，而不是表示一个新的子空间。

还有一个可以直接用上的优化：如果在第 $k$ 层接回旧链，那么第 $k$ 维及之后的空间此前已经出现过，不必再次收集它们的指纹。只需要用更新后的系数计算前 $k-1$ 个正维空间的指纹。若 $x\notin U_d$，才需要计算全部 $d+1$ 个。

下面是实现中的核心部分，数组下标从 $0$ 开始。mul、sqr 分别是域乘法与平方，^ 是域加法：

// c[0..d-1]：旧空间链的系数。
// nc：新系数的临时数组。
// changed：本次需要收集指纹的低维空间数量。

F y(a);
nc[0] = y;

int len = 1;
int changed = -1;

for (int i = 0; i < d; ++i) {
    if (y == c[i]) {
        // 第 i+1 维起，新旧空间完全相同。
        changed = i;
        break;
    }

    F p = mul(y, c[i]);
    nc[len++] = sqr(c[i]) ^ p;
    y = sqr(y) ^ p;
}

if (changed == -1) {
    d = len;
    changed = len;
}

// 后续系数保持原样。
for (int i = 0; i < len; ++i)
    c[i] = nc[i];

F h = z;
for (int i = 0; i < changed; ++i) {
    h = sqr(h) ^ mul(c[i], h);
    hashes[i].push_back(h);
}

如果追加的数是零，则所有正维后缀空间都不变，只需要记录零空间出现过。零空间能由某个非空区间生成，当且仅当数组中出现过零，因此最后用一个布尔值单独计数即可；不要因为维护时补了辅助空间 $U_0$，就无条件把它算入答案。

去重、复杂度与碰撞概率

对每个正维空间 $S$，保存二元组 $(\dim S,P_S(z))$。实现中按维度分别开数组，因此只需要存储 $128$ 位的 $P_S(z)$。

不使用比较排序，而是对每个数组进行逐字节基数排序。一个指纹固定占 $16$ 字节，经过 $16$ 轮稳定计数排序即可完成排序，再统计相邻不同元素的数量。这样，去重不会引入 $\log n$，也不依赖哈希表的期望性能。

每次追加元素，最多扫描 $b$ 层，每层只进行常数次域运算。产生的指纹总数至多为 $nb$，基数排序也是线性时间。因此，总时间复杂度为 $O(nb)$，总空间复杂度为 $O(nb)$，其中维护当前空间链本身只需要 $O(b)$ 空间。更精确地，若所有输入向量的总秩为 $D$，时间上界是 $O(n(1+D))$。

在本题固定 $b=32$ 的模型下，这是关于 $n$ 的 $\Theta(n)$ 算法，已经达到读入所需的线性下界。不过，若把维度也作为可变参数，不能仅凭存在 $O(nb)$ 个候选空间，就断言计数问题具有 $\Omega(nb)$ 下界——输出毕竟只有一个数。

最后分析随机性。设 $S\ne T$，且它们的维度同为 $d$。两个子空间多项式都是首一的 $2^d$ 次线性化多项式，最高次项抵消，因此非零多项式 $P_S-P_T$ 的次数至多为 $2^{d-1}$。若 $z$ 在 $K$ 中独立于输入均匀随机选取，那么这两个空间发生指纹碰撞的概率至多为 $2^{d-1}/2^{128}$。

每个固定维度至多出现 $n$ 个候选空间，对所有同维空间对使用并集界，得到单组测试的错误概率上界：

$$ \Pr[\text{发生误判}] \le \frac{\binom n2\sum_{d=1}^{b}2^{d-1}}{2^{128}} = \frac{\binom n2(2^b-1)}{2^{128}}. $$

在 $b=32$、所有测试长度之和不超过 $10^5$ 时，对整份输入使用同样的并集界，结果小于 $6.4\times10^{-20}$。这仍然是有极小错误概率的随机化算法，而不是绝对无碰撞的算法；但空间链的维护、维度变化以及线性相关性判断全部是精确的，随机性只影响最后的去重，发生碰撞时也只可能少算。

完整实现使用不可约多项式 $t^{128}+t^7+t^2+t+1$ 构造 $\mathbb F_{2^{128}}$，这个模多项式也用于标准的 GCM 二元域构造。([NIST Publications][2]) 域乘法通过常数次无进位乘法及位运算完成，代码面向支持 PCLMULQDQ 的 x86-64 GCC 环境；这里的域乘法不能替换成普通整数乘法。

提交记录 https://qoj.ac/submission/2936399 ，CCPC Final 的题就是简单。