- \(\mathtt{Description}\)：
给定 \(n\) 和一个长度为 \(2^n\) 的数组 \(A\) (从 \(0\) 标号).
有一个初始为 \(0\) 的变量 \(x\) . 不断操作, 每次操作以 \(\frac {A_i}{\sum_{j=0}^{2^n-1} A_j}\) 的概率将 \(x\) 变成 \(x\ xor\ i\) .
对于所有 \(i\in[0,2^n)\) , 求出 \(x\) 第一次变成 \(i\) 的期望操作次数.
\(n\leqslant 18, 1\leqslant A\leqslant 1000\)
- \(\mathtt{Solution}\)：
类似随机游走，令 \(f_i\) 为第一次操作到 \(i\) 的期望操作次数，\(p_i\) 为每次操作数为 \(i\) 个概率，显然有：
（上面两个式子的条件位置差了一像素，很难受，有没有人教教怎么改。/kk）
显然可以高斯消元，不过是 \(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)\)，很好写。