记 (f_S) 表示第一次到达 (S) 状态的期望步数,(p_{{i}}) 表示将当前状态异或上 ({i}) 的概率，则有：
[egin {align*}
f_{emptyset} & = 0 \
f_S & = 1 +sum_{jigoplus k}f_jp_k \
end {align*}
]
记 (hat{f}) 表示 (f) 的 (operatorname{FWT}) 结果，其余同理，则有：
[hat{f}=hat{I}+hat{f}hat{p}+c
]
其中，(I=sum_S x^S)，(c) 是一个用于修正 (f_{emptyset}) 的常数。
移项，得：
[hat{f}_S(1-hat{p}_S) = hat{I}_S+c
]
注意到 (hat{p}_{emptyset} = 1, hat{I}_{emptyset}=2^n)，故 (c = -2^n)。且 (forall S eqemptyset)，有 (hat{p}_S < 1)，故：
[egin {align*}
hat{f}_S & = frac {-2^n}{1-hat{p}_S} \
& = frac {-2^n}{1-sum_That{p}_Tleft(-1
ight)^{|Scap T|}} \
& = frac {-2^n}{2sum_{iin S}p_i}
end{align*}
]
把答案手动 (operatorname {IFWT}) 回去，有：
[egin {align*}
f_S & = frac 1{2^n}sum_Tleft(-1
ight)^{|Scap T|}hat{f}_T \
& = frac {hat{f}_{emptyset}}{2^n} - sum_{T
eqemptyset}left(-1
ight)^{|Scap T|}frac 1{2sum_{iin T}p_i}
end{align*}
]
由 (f_{emptyset}=frac 1{2^n}sum_T hat{f}_T=0) 有 (hat{f}_{emptyset}=-sum_{T eqemptyset}hat{f}_T)，代入化简，得：
[egin {align*}
f_S & = sum_{T
eqemptyset}left(1-left(-1
ight)^{|Scap T|}
ight)frac 1{2sum_{iin T}p_i} \
& = sum_{T
eqemptyset}frac{[|Scap T|mod 2=1]}{sum_{iin T}p_i}\
end {align*}
]
注意到 (sum p) 很小，直接大力 dp 就好了，复杂度 (operatorname O(nsum p))。
可以使用多项式技巧继续优化，在本题中没有必要。