Solution不好做的地方在于每一对朋友的友谊值是不同的，于是考虑将其统一为一个数。比较好想的就是将他们的初始友谊值提前计算，即对于每一次远足，设总情况为\(S=\frac{n\times(n-1)}{2}\)，总的初始友谊值为\(w=\sum_{i=1}^{m}f_i\)，假设友谊值不变，获得的期望友谊值为\(\frac{w}{

考虑分别计算\(p\)和\(q\)。按照期望的定义，\(q\)应该等于方案的总数，也就是\(s^k\)，其中\(s\)表示一共有多少个不同的组。考虑如何求\(p\)，我们先只计算第\(i\)组对\(p\)的贡献。如果第\(i\)组一共被选了\(1\)次，那么贡献为：\[g=f_i\timesC_{k}^{1}\times(s-1)^{

Solution发现我们并不关下每一组人到底是哪些人。不妨从dp的角度去考虑这个问题。设\(p=2/(n\times(n-1))\)，\(dp_i\)为选了\(i\)组人后期望得到的友谊值。第\(i\)次选人，有\(1-p\timesm\)的概率选中不是朋友的一组人。设\(x_j\)为此时第\(j\)组的期