描述

---

分析

• 轉(zhuǎn)化為二進(jìn)制按位來計(jì)算, 最后把每一位的加起來
• f[i]表示i到n的期望路徑長度, d[i]表示i的度
• 因?yàn)閕的期望是由i走到的點(diǎn)狀態(tài)轉(zhuǎn)移得到的, 所以在計(jì)算概率時(shí)應(yīng)該用i的度來算
• 如果i到j(luò)的邊的權(quán)值的第 BIT 位是0, 任何數(shù)異或0都是它本身, 所以f[i] = f[j] / d[i] + …
• 如果i到j(luò)的邊的權(quán)值的第 BIT 位是1, 異或一相當(dāng)于取反. 所以f[i] = (1-f[j]) / d[i] + …
• 然后列出f[i]的方程, 移項(xiàng)使所有的f值在左邊, 右邊剩一堆常數(shù), 就可以高斯消元了.
• 有n個(gè)方程, n個(gè)變量. 解出X, ans = sum{X[0] * (1 << BIT) | 0 <= BIT < 30 即可}

代碼

https://code.csdn.net/snippets/619507

總結(jié)

以上是生活随笔為你收集整理的BZOJ-2337-XOR和路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。