洛谷 P3802 小魔女帕琪 解题报告

时间：2021-10-25 11:45:47

P3802 小魔女帕琪

题目背景

从前有一个聪明的小魔女帕琪，兴趣是狩猎吸血鬼。

帕琪能熟练使用七种属性（金、木、水、火、土、日、月）的魔法，除了能使用这么多种属性魔法外，她还能将两种以上属性组合，从而唱出强力的魔法。比如说为了加强攻击力而将火和木组合，为了掩盖弱点而将火和土组合等等，变化非常丰富。

题目描述

现在帕琪与强大的夜之女王，吸血鬼蕾咪相遇了，夜之女王蕾咪具有非常强大的生命力，普通的魔法难以造成效果，只有终极魔法：帕琪七重奏才能对蕾咪造成伤害。帕琪七重奏的触发条件是：连续释放的7个魔法中，如果魔法的属性各不相同，就能触发一次帕琪七重奏。

现在帕琪有7种属性的能量晶体，分别为\(a_1,a_2,a_3,a_4,a_5,a_6,a_7\)(均为自然数)，每次释放魔法时，会随机消耗一个现有的能量晶体，然后释放一个对应属性的魔法。

现在帕琪想知道，她释放出帕琪七重奏的期望次数是多少，可是她并不会算，于是找到了学\(OI\)的你

输入输出格式

输入格式：

一行7个数字，\(a_1,a_2,a_3,a_4,a_5,a_6,a_7\)

输出格式：

一个四舍五入保留3位的浮点数

数据范围:

对于30%的测试点，\(a_1+a_2+a_3+a_4+a_5+a_6+a_7<=10\)

对于100%的测试点，\(a_1+a_2+a_3+a_4+a_5+a_6+a_7<=10^9\)

UDT：2018.9.25

之前写的有不小问题，居然没人提。。

今天被期望虐惨了，去洛谷找了道颜色最低的期望题

然后...不会洛谷 P3802 小魔女帕琪 解题报告

好吧，正题...

首先直接考虑对于取的前7个能量晶体

设\(N=\sum_{i=1}^7 a_i\)

考虑前7个一连串取出了\(a_1,a_2,a_3,..a_7\)的概率

为\(\frac{a_1}{N} \times \frac{a_2}{N-1} \times \frac{a_3}{N-2} \times \frac{a_4}{N-3} \times \frac{a_5}{N-4} \times \frac{a_6}{N-5} \times \frac{a_7}{N-6}\)

因为是条件概率，所以样本空间减少了(n-x)

对条件概率：

简单一点的解释是，B在A发生的条件下发生的概率。

举个栗子，掷色子第一次投6概率为1/6，为A事件，第二次投6概率仍为1/6，为B事件。如果把两次投掷产生的一个结果算成一个最终状态，那么连续的状态AB发生的概率为1/36，也即是B在A发生的条件下发生的概率。

然后我们对取出1-7的式子发现，如果我们不按1-7的顺序取，分子分母并没有变化

那么直接按照排列组合，把所有顺序的全部统计

即\(7! \times \frac{a_1}{N} \times \frac{a_2}{N-1} \times \frac{a_3}{N-2} \times \frac{a_4}{N-3} \times \frac{a_5}{N-4} \times \frac{a_6}{N-5} \times \frac{a_7}{N-6}\)

但其实后面每七位对应的答案都是这样，下面讲为什么

在考虑之后怎么取之前，我们先想一个问题。

你班要选择投票一个人，在班花喵面前吃巧克力，然后班主任拿了一个盒盒让你们摸球球，里面有1个红球和29个白球（你班30人），抽到红球的人就有了这个至高无上的权利，一个个的去抽，那么顺序不一样的话，是公平的吗？？

当然...是了

第一个人抽中的概率是 \(\frac {1}{30}\)

第二个人抽中的概率是 \(\frac {29}{30} \times \frac {1}{29}\)

第三个人抽中的概率是 \(\frac {29}{30} \times \frac {28}{29} \times \frac {1}{28}\)

...

有了这些我们可以感性理解在这个题中每七位都是一样的统计了

以上只是提供一个感性的类似的说明方法，和下面的并非直接相关

然后我们考虑用类似的方法把它说清楚

如果第一个取出\(a_1\)

我们考虑它取出的合法的第2-8个，就可以再次放招了

概率为

\(\frac{a_1}{N} \times \frac{a_2}{N-1} \times \frac{a_3}{N-2} \times \frac{a_4}{N-3} \times \frac{a_5}{N-4} \times \frac{a_6}{N-5} \times \frac{a_7}{N-6} \times \frac{a_1-1}{N-7}\)

同理组合有\(7!\)种(这\(7!\)是确定了首位而\(2-8\)不定的情况)

如果第一个取\(a_2\)

概率为

\(\frac{a_2}{N} \times \frac{a_1}{N-1} \times \frac{a_3}{N-2} \times \frac{a_4}{N-3} \times \frac{a_5}{N-4} \times \frac{a_6}{N-5} \times \frac{a_7}{N-6} \times \frac{a_2-1}{N-7}\)

我们把第一个取出的7种可能加在一起

发现末项加起来化简是1

即\(\sum_{i=1}^7 \frac{a_i-1}{N-7}=1\)

于是对第2-8位的贡献化简结果就是\(7! \times \frac{a_1}{N} \times \frac{a_2}{N-1} \times \frac{a_3}{N-2} \times \frac{a_4}{N-3} \times \frac{a_5}{N-4} \times \frac{a_6}{N-5} \times \frac{a_7}{N-6}\)

所以最终答案就是（乘上了\(N-6\)项）

\(7! \times \frac{a_1}{N} \times \frac{a_2}{N-1} \times \frac{a_3}{N-2} \times \frac{a_4}{N-3} \times \frac{a_5}{N-4} \times \frac{a_6}{N-5} \times {a_7}\)

Code：

#include <cstdio>

double a[8],s,ans=1;

int main()

{

    for(int i=1;i<=7;i++)

    {

        scanf("%lf",a+i);

        s+=a[i];

    }

    for(int i=1;i<=6;i++)

        ans=ans*a[i]/(s+1-i)*double(i);

    ans=ans*a[7]*7.0;

    printf("%.3lf\n",ans);

    return 0;

}

2018.7.16

相关文章