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

作者: wjyyy 分类: 数学,概率期望,解题报告 发布时间: 2018-07-16 22:06

点击量:22

 

   需要推导公式的期望

 

题目背景

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

 

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

 

题目描述

现在帕琪与强大的夜之女王,吸血鬼蕾咪相遇了,夜之女王蕾咪具有非常强大的生命力,普通的魔法难以造成效果,只有终极魔法:帕琪七重奏才能对蕾咪造成伤害。帕琪七重奏的触发条件是:连续释放的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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */