洛谷 P3802 小魔女帕琪 题解【概率期望】

点击量：123

   需要推导公式的期望

目录

题目背景

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

 

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

 

题目描述

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

 

现在帕琪有7种属性的能量晶体，个数分别为a1,a2,a3,a4,a5,a6,a7(均为自然数)，每次释放魔法时，会随机消耗一个现有的能量晶体，然后释放一个对应属性的魔法。

 

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

 

输入输出格式

输入格式：

一行7个数字，a1,a2,a3,a4,a5,a6,a7

 

输出格式：

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

 

输入输出样例

输入样例#1：

1 1 1 1 1 1 1

输出样例#1：

1.000

说明

样例说明:

显然一定会触发一次帕琪七重奏

 

数据范围:

对于30%的测试点，a1+a2+a3+a4+a5+a6+a7<=10

 

对于100%的测试点，a1+a2+a3+a4+a5+a6+a7<=10^9

 

by-szc

题解：

   初始时，对于一个球i，女猪脚有

$ \frac {a_{i_1}}{\sum\limits_{j=1}^7a_j}$

的几率拿到它。而第二个选择异于$ a_{i_1}$的$ a_{i_2}$的概率就是

$ \frac {a_{i_2}}{\sum\limits_{j=1}^7a_j-1}$

   以此类推，那么在前7个触发的概率就是

$ \prod\limits_{i=1}^7\frac {a_i}{\sum\limits_{j=1}^7a_j+1-i}$

   而前7个如果互不相同，则有$ 7!$种排列，因此还要在这个公式的基础上乘上$ 7!$。

   可是这只是对前7个而言，也就是从第8个开始，如果前7个构成了一个大招，并且第$ i$个和第$ i-7$个是一种能量球，接下来仍然可以释放一个。不过我们在前面乘了7!，所以此时的状态可以代表第2~8个球的各种组合，那么接下来凑出与$ i-7$相同数的概率在乘了$ 7!$的基础上，因为1,8号位出现相同元素的概率为$ \frac{a_1}n\times \frac{a_1-1}{n-7}$，种类有7种，那么只需要乘上各种数出现的概率之和就可以了。而这个和的公式是

$ \sum\limits_{i=1}^7\frac{a_i-1}{n-7}$

   把它展开我们发现：

$ \frac{a_1-1}{n-7}+\frac{a_2-1}{n-7}+\ldots + \frac{a_7-1}{n-7}=\frac{n-7}{n-7}=1$

   因此无论这个数列有多长，在这个长度下触发大招的概率总是

$ \prod\limits_{i=1}^7\frac {a_i}{\sum\limits_{j=1}^7a_j-1-i}$

   如果设$ \sum\limits_{j=1}^7a_j$为$ n$，那么在这整段区间内有$ n-6$段是有效的，也就是说，这$ n-6$段放出大招的概率都是上式，最终结果就是

$ (n-6)\prod\limits_{i=1}^7\frac {a_i}{n+1-i}$

   所以这是一个需要推很多很多很多公式的代码量极短的期望好题。

Code：

#include<cstdio>
#include<cstring>
int a[8];
int main()
{
    int sum=0;
    for(int i=1;i<=7;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    if(sum<7)
    {
        puts("0.000");
        return 0;
    }
    double tt=720.0*7.0;//7!
    for(int i=1;i<=7;i++)
        tt*=(a[i]*1.0)/((sum-i+1)*1.0);
    printf("%.3lf\n",tt*(sum-6.0));
    return 0;
}