CF601C Kleofáš and the n-thlon
根据全概率公式,期望就是概率和权值的乘积,所以只需要算出 场总分小于 的概率最后乘以 就可以了。
需要注意因为每一个得分只出现一次,所以计算是与 有关的。
容易发现,我们需要求的概率就是所有得分为小于 的概率之和,所以这个题目就转换为了求出每一个得分的概率了。
设 表示前 场比赛得分为 的概率,那么显然有:
考虑把 做一个前缀和优化,那么复杂度就是 。
根据全概率公式,期望就是概率和权值的乘积,所以只需要算出 场总分小于 的概率最后乘以 就可以了。
需要注意因为每一个得分只出现一次,所以计算是与 有关的。
容易发现,我们需要求的概率就是所有得分为小于 的概率之和,所以这个题目就转换为了求出每一个得分的概率了。
设 表示前 场比赛得分为 的概率,那么显然有:
考虑把 做一个前缀和优化,那么复杂度就是 。