题意

给定一 $k$ 维位线性空间，需要找出向量序列 $\vec{a}_1,\vec{a}_2,\cdots,\vec{a}_n$，

使之张成的线性子空间维度为 $t$，且子空间中不包含 $\vec{X}$。

$\forall t\in[1,k]$，求方案数。

题解

首先特判 $\vec{X}=\vec{0}$ 的情况：此时等价于 $\vec{a}_1,\vec{a}_2,\cdots,\vec{a}_n$ 线性无关。

对于 $\vec{a}_1,\vec{a}_2,\cdots,\vec{a_i}$，其张成的线性子空间维度为 $i$，包含 $2^i$ 个向量。

$\vec{a}_{i+1}$ 不能是这 $2^i$ 个向量中的任意一个，因此答案即

$$\prod_{i=0}^{n-1}(2^k-2^i)$$

接下来考虑 $\vec{X}\not=\vec{0}$ 的情况，显然答案和 $\vec{X}$ 具体是什么无关。

同样考虑逐步添加向量，设当前线性子空间 $V$ 的维度为 $i$。

• 若添加下一个向量后 $V$ 维度不变，则下一个向量在 $V$ 中，
  有 $|V|-1=2^i-1$ 种可能。
• 否则，由于 $\vec{X}\notin V$，设 $W=V\cup\{\vec{a}+\vec{X}|\vec{a}\in V\}$，
  则下一个向量一定不在 $W$ 中，否则就会表出 $\vec{X}$ 或使维度不增加，
  有 $2^k-|W|=2^k-2^{i+1}$ 种可能。

总上，因为加入了 $n$ 个向量，最终维度为 $t$，
有 $t$ 次加入使维度增加，其余 $n-t$ 次加入使维度不变，答案即

$$\left(\prod_{i=0}^{t-1}(2^k-2^{i+1})\right)\sum_{\sum_{i=1}^tb_i=n-t}\prod_{i=1}^t(2^i-1)^{b_i}$$ $$=[x^{n-t}]\prod_{i=1}^t\dfrac{2^k-2^i}{1-(2^i-1)x}$$

$n$ 很大，但分母是已因式分解的多项式，考虑线性递推

$$[x^n]\dfrac{1}{1-ax}=a^n$$ $$[x^n]\dfrac{1}{(1-ax)(1-bx)}=\sum_{k=0}^na^kb^{n-k}=b^n\sum_{k=0}^n\left(\dfrac{a}{b}\right)^k$$ $$=b^n\dfrac{\left(\dfrac{a}{b}\right)^{n+1}-1}{\left(\dfrac{a}{b}\right)-1}=\dfrac{a^{n+1}}{a-b}+\dfrac{b^{n+1}}{b-a}$$

由于求和满足线性性，归纳可得

$$[x^n]\prod_{1\le i

因此答案的通项为

$$[n\ge t]\left(\prod_{i=1}^t(2^k-2^i)\right)\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle\prod_{\small j\not=i\atop1\le j\le t}(2^i-2^j)}$$

显然 $\displaystyle\left(\prod_{i=1}^t(2^k-2^i)\right)$ 可以 $\Theta(n)$ 递推。于是设

$$f_t=\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle\prod_{\small j\not=i\atop1\le j\le t}(2^i-2^j)}\qquad(t\le n)$$

将下面的 $\prod$ 拆开

$$f_t=\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle\left(\prod_{j=1}^{i-1}(2^i-2^j)\right)\left(\prod_{j=i+1}^t (2^i-2^j)\right)}$$

将 $2^i$ 从 $\prod$ 中提出来

$$f_t=\sum_{i=1}^t\dfrac{(2^i-1)^{n-1}}{\displaystyle2^{i(t-1)}\left(\prod_{j=1}^{i-1}(1-2^{j-i})\right)\left(\prod_{j=i+1}^t (1-2^{j-i})\right)}$$

$$f_t=\sum_{i=1}^t\dfrac{2^{-i(t-1)}(2^i-1)^{n-1}}{\displaystyle\left(\prod_{j=1}^{i-1}(1-2^{-j})\right)\left(\prod_{j=1}^{t-i} (1-2^{j})\right)}$$

分母已经是卷积形式了，套路性的拆开 $2^{-i(t-1)}$

$$-i(t-1)=\dbinom{t-i}{2}-\dbinom{t}{2}-\dbinom{i}{2}$$

$$f_t=2^{\binom{t-i}{2}}\sum_{i=1}^t\dfrac{2^{-\binom{i}{2}}(2^i-1)^{n-1}}{\displaystyle\prod_{j=1}^{i-1}(1-2^{-j})}\times\dfrac{2^{\binom{t-i}{2}}}{\displaystyle\prod_{j=1}^{t-i}(1-2^j)}$$

NTT $\Theta(n\log n)$ 卷积即可。即

$$a_i=\dfrac{(2^i-1)^{n-1}}{\displaystyle\prod_{j=1}^{i-1}(1-2^{-j})},b_i=\dfrac{1}{\displaystyle\prod_{j=1}^i(1-2^j)},c_i=2^{\binom{i}{2}}$$

$$f_t=c_t\sum_{i=1}^t(a_ic_i^{-1})(b_{n-i}c_{n-i})$$

$$ans=\displaystyle\mathop{\operatorname{xor}}\limits_{t=1}^{\min(k,n)}\left(f_t\prod_{i=1}^t(2^k-2^i)\right)$$

预处理 $a_i,b_i,c_i$ 有轻微卡常注意。