类似随机游走，令 \(f_i\) 为第一次操作到 \(i\) 的期望操作次数，\(p_i\) 为每次操作数为 \(i\) 个概率，显然有：
显然可以高斯消元，不过是 \(O(2^{3n})\) 的，寄飞。
考虑到转移过程中有类似异或卷积的东西，令 \((f*p)_i\) 为 \(\sum\limits_{j\;\text{xor}\;k\ =i\ }f_jp_k\)，那么 \(i\neq 0\) 时，\((f*p)_i+1=f_i\)。
考虑 \((f*p)_0\) 的值。由于 \(\sum\limits_ip_i=1\)，于是根据 FWT 的线性性：
由于 \(f_0=0\)，那么 \((f*p)_0=2^n-1\)，所以用括号表示集合幂级数的话：
接下来就很套路了，由于卷积的每项都带有 \(f_i\)，那么给 \(p_0\) 减去 \(1\)，相当于给每位减去了 \(f_i\)，因为 \(i\;\text{xor}\;0\ =\ i\)：
这是 \(F*P=F'\) 的形式，那么 \(F=F'*P^{-1}\)。后面两个都已知，FWT 后点值相除就好了……吗？
注意到 \(\text{FWT}(P)_0=\text{FWT}(F')_0=0\)，\(\text{FWT}(F)\) 第 \(0\) 位你填个啥？
注意到其他位都是对的，那一位可以看作一个变量，肯定有一个数填 \(c\) 到这一位使得 IFWT 后是对的。那么我们直接对 \(\left(0\quad \dfrac{\text{FWT(F')}_1}{\text{FWT(P)}_1}\quad \dfrac{\text{FWT(F')}_2}{\text{FWT(P)}_2}\quad ...\quad \dfrac{\text{FWT(F')}_{2^n-1}}{\text{FWT(P)}_{2^n-1}}\right)\) 做 IFWT，由于第 \(0\) 位改变，影响的是每一项，而 IFWT 回去的结果是 \(f'(0)\) 而不是 \(f(0)=0\)，所以给 \(f'\) 整体减去 \(f'(0)\) 所得就是答案了。
复杂度 \(O(n2^n)\)，很好写。