一眼无穷嵌套DP
设\(f[i]\)表示从\(i\)到\(N\)的期望
然后你会发现推不走，为什么？因为乘法对异或没有分配率！
但是不要怀疑我们的整体套路，我们应该从位运算的另一trick入手：考虑每一位
试想，如果我们列出了所有路径的样本空间（这当然是不可能的），知道了每个样本空间的xor和，乘以对应的概率并求和那么就是答案
对于每一个样本空间的xor和，我们将其每一位拆开，显然对于第\(i\)位，只由这个空间里面每个边权的权值的第\(i\)位影响，所以我们对每一位进行无穷嵌套DP，然后最后加总也是答案
于是我们枚举bit，把每条边的权值换为其对应的第\(i\)位数字，然后求解到达\(N\)的xor和为\(1\)的概率是多少即可
标签：xor,路径,样本空间,权值,XOR,DP From： https://www.cnblogs.com/dingxingdi/p/18018384