类似随机游走，令 \(f_i\) 为第一次操作到 \(i\) 的期望操作次数，\(p_i\) 为每次操作数为 \(i\) 个概率，显然有：
\[f_i=\begin{cases}0&i=0\\1+\sum\limits_{j\;\text{xor}\; k\ =\ i}p_jf_k &i\neq 0\end{cases} \]显然可以高斯消元，不过是 \(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 的线性性：
\[\begin{aligned}\sum\limits_i(f*p)_i&=\sum\limits_{i}f_i\\\sum\limits_{i\neq 0}(f*p)_i+(f*p)_0&=\sum\limits_{i\neq 0}f_i+f_0\\(f*p)_0&=f_0+2^n-1\end{aligned} \]由于 \(f_0=0\)，那么 \((f*p)_0=2^n-1\)，所以用括号表示集合幂级数的话：
\[(f_0\quad f_1\quad f_2\quad...\quad f_{2^n-1})*(p_0\quad p_1\quad p_2\quad ...\quad p_{2^n-1})=(f_0+2^n-1\quad f_1-1\quad f_2-1\quad ... \quad f_{2^n-1}-1) \]接下来就很套路了，由于卷积的每项都带有 \(f_i\)，那么给 \(p_0\) 减去 \(1\)，相当于给每位减去了 \(f_i\)，因为 \(i\;\text{xor}\;0\ =\ i\)：
\[(f_0\quad f_1\quad f_2\quad...\quad f_{2^n-1})*(p_0-1\quad p_1\quad p_2\quad ...\quad p_{2^n-1})=(2^n-1\quad -1\quad -1\quad ... \quad -1) \]这是 \(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)\)，很好写。
标签：...,XOR,limits,AGC034F,sum,RNG,text,FWT,quad From： https://www.cnblogs.com/Ender32k/p/17569329.html