参考自 wlzhouzhuan。
考虑枚举序列的标准基底。设秩为 \(k\)，其中元素的最高位分别为 \(a_0 < a_1 < \dots < a_{k-1}\)。
于是，贡献由三部分组成：秩为 \(k\) 的序列个数、标准基底个数，以及最大异或和的期望值。
秩为 \(k\) 的序列个数是经典问题，在此处已经讨论过（不过这里先不考虑基是哪些元素），于是直接给出结论： \[ 2^{k(k-1)/2} (k!)_2 \binom nk_2 \]
对应的标准基底个数，由于除了钦定的 \(k\) 位以外其他位都可以随意选定，于是显然就是 \[ \prod_{i=0}^{k-1} 2^{a_i-i} = 2^{-k(k-1)/2} \prod_{i=0}^{k-1} 2^{a_i} \]
最大异或和的期望值，也就是基底的期望异或和。其中钦定的 \(k\) 位必然为 \(1\)，其余可能出现在基底中的位各有 \(1/2\) 的概率为 \(1\)。于是： \[ \frac12\left(2^{a_{k-1}+1}-1+\sum_{i=0}^{k-1}2^{a_i}\right) \]
那么我们主要要计算 \[ \frac12\left(2^{a_{k-1}+1}-1+\sum_{i=0}^{k-1}2^{a_i}\right) \prod_{i=0}^{k-1} 2^{a_i} \]
对于 \(-1/2\) 项，有 \[ -\frac12 [x^k] \prod_{i=0}^{m-1}(1+2^i x) = -2^{k(k-1)/2-1} \binom mk_2 \]
对于 \(\frac12 \sum_i 2^{a_i}\) 项，一个很棒的做法是看成 \(2^m-1\) 中减去其他不在基中的项，也就是可以看成选 \(k+1\) 个： \[ (2^m-1) 2^{k(k-1)/2-1} \binom mk_2 - (k+1) 2^{k(k+1)/2-1} \binom m{k+1}_2 \]
对于 \(2^{a_{k-1}}\) 项，我们可以另列 \[ F(x) = \sum_{r=0}^{m-1} 2^{2r} \prod_{i=0}^{r-1} (1+2^ix) \]
这也是 q-D-finite 的。当然，如果你愿意，同样可以表为 q-二项式系数。