BZOJ2337 [HNOI2011]XOR和路径 高斯消元 图论 期望概率

BZOJ2337 [HNOI2011]XOR和路径 高斯消元

题目链接 一遍填以前的坑,一遍翻达哥的题表,结果就做了一堆高斯消元= = 考虑到二进制上每一位都是独立的,我们可以按位分别计算概率。 还是倒着做,设f[i]:从i点到达n点,该二进制位异或和为1的概率。 当遇到一条二进制为1的边时,意味着通过这条边,按照定义,概率应该取对立面,所以f[i]=p[i]···
BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元 图论 期望概率

BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元

  题目链接 和BZOJ3270比较相似,都是在图上高斯消元来转移状态。 观察数据范围,可以很明显地看出来必须先Tarjan缩点,之后在强连通分量里面进行高斯消元。 一开始仿照3270写了个正着推出的式子,发现不太好搞,于是重新倒着想了一遍。 设f[i]:从i点出发走到终点的期望步数,则f···