CF1603F

$x=0$ 怎么做？即 $n$ 个向量全部线性无关，每加入一个向量 $\dim$ 加一，则答案即为 $\prod\limits_{1\le i\le n}\left(2^k-2^{i-1}\right)$，因为前 $i-1$ 个向量张成空间有 $2^{i-1}$ 个元素。

否则，可以发现 $x$ 取任何值答案一样，否则将所有不同的位全部取反，显然构成双射。不妨让 $x=1$ 来讨论。取序列 $a$ 一线性基 $B_{1\sim d}$，则限制即向量组 $(B_1,\cdots,B_d,x)$ 所有数线性无关。则 $x$ 为主元位为 $1$ 的基底，类似于 $x=0$ 的情况，对于第 $2\sim d+1$ 个基底向量的选择方案数为 $\prod\limits_{2\le i\le d+1} \left(2^k-2^{i-1}\right)=\prod\limits_{1\le i\le d} \left(2^k-2^i\right)$。

其余 $n-d$ 个数，枚举每个数在第几个基底向量被确定后插入；若在第 $i$ 个基底向量确定后被插入，则方案数即为 $2^i$，故方案数为

即最终答案为

可以在 $\mathcal{O}(k)$ 复杂度内完成计算。