agc034f专题

AtCoder AGC034F RNG and XOR (概率期望、FWT)

题目链接 https://atcoder.jp/contests/agc034/tasks/agc034_f 题解 无论多水的题我都不会啊.jpg 首先考虑一个图上随机游走的经典问题,无向图求从\(0\)号点出发随机游走到每个点的期望时间。做法是显然答案等于从每个点走到\(0\)号点的期望时间,然后列方程高斯消元。 设答案向量为\(\textbf{x}\), 则有\(x_i=\sum_{j\ \