根据全概率公式,期望就是概率和权值的乘积,所以只需要算出 nn 场总分小于 i=1nci\sum\limits_{i=1}^n c_i 的概率最后乘以 m1m-1 就可以了。

需要注意因为每一个得分只出现一次,所以计算是与 cic_i 有关的。

容易发现,我们需要求的概率就是所有得分为小于 i=1nci\sum\limits_{i=1}^n c_i 的概率之和,所以这个题目就转换为了求出每一个得分的概率了。

fi,jf_{i,j} 表示前 ii 场比赛得分为 jj 的概率,那么显然有:

fi,j=k=1kcimin(m,j)fi1,jkm1f_{i,j}=\sum\limits_{k=1\wedge k\ne c_i}^{\min(m,j)}\dfrac{f_{i-1,j-k}}{m-1}

考虑把 fi,jf_{i,j} 做一个前缀和优化,那么复杂度就是 O(n2m)O(n^2m)