CF1556F Sports Betting

DP、正难则反

首先很明显可以转化为求每个点的获胜概率。

直接考虑获胜的情况，发现由于获胜具有传递性，一个点的全局获胜情况可以会有其他点的局部获胜情况转移得来。

由于每个点有一个权值 \(a_i\)，每个点不是等价的，也就是说到达点的不同会影响答案，这里只能将边全部状压，复杂度为 \(\mathcal O(2^{n^2})\)。

点之间的转移是由于“获胜具有传递性”导致的，考虑取其反命题，可以发现"不获胜"不具有传递性，甚至必须同时满足，所以再从不获胜的角度考虑。

全部获胜的概率应该等于 \(1-\) 部分不获胜的概率，可以考虑枚举这个集合。那么就会有一部分获胜一部分不获胜，前者是一个子问题关系，后者由于“必须同时满足”，应该是直接将概率相乘，这是可做的。

剩下就与题解一样了。

所以我认为，“正难则反”其实是因为“正”的时候所满足的一些性质不好处理，而“反”所满足的一些性质截然不同，可能就易于处理了。