CF1603F

· · 题解

否则，可以发现 $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$，故方案数为 $$ \begin{aligned} &\left[x^{n-d}\right]\prod\limits_{0\le i\le d} \left(\sum\limits_{j\ge 0}2^{ij}x^j\right)\\ =&\left[x^{n-d}\right]\prod\limits_{0\le i\le d}\frac{1}{1-2^ix}\\ =&\begin{bmatrix}n\\n-d\end{bmatrix}_2 \end{aligned} $$ 即最终答案为 $$ \sum\limits_{0\le d\le \min(n,k)} \begin{bmatrix}n\\d\end{bmatrix}_2 \left(\prod\limits_{1\le i\le d}\left(2^k-2^i\right)\right) $$ 可以在 $\mathcal{O}(k)$ 复杂度内完成计算。