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