参考自 wlzhouzhuan。
考虑枚举序列的标准基底。设秩为 k，其中元素的最高位分别为 a0<a1<⋯<ak−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-二项式系数。