题解 P3802 【小魔女帕琪】

· · 题解

题意简述：

有 a_i 个 i（1 \leq i \leq 7），每次从所有未选的中随机选出一个，接在最后面，求连续 7 个互不相同的数的组数的期望值。

题解：

记 N=a_1+a_2+\cdots+a_7。

事实上，任意连续 7 位构成终极魔法的概率是一样的。

这是因为，尽管帕琪是依次使用各个魔法，但实际上，我们可以认定只需要从一个长度为 N 的数列中求出连续 7 个互不相同的数的组数的期望值。

于是，连续 7 个数 x_{i+1},x_{i+2},\dots,x_{i+7} 能否成为终极魔法与剩余的 N-7 个数的相对顺序无关。

因此，我们并不需要关心是否有条件概率来干扰计算，这个序列在遍历所有可能情形后，关于我们所要求的——连续 7 个互不相同的数的组数的期望值，是期望平均的。

即在所有可能情况下，连续 7 个互不相同的数在序列中是平均分布的。

所以，任意连续 7 位构成终极魔法的概率是一样的。

深刻理解了这一点后，这道题就很简单了。

而一共有 N-6 组连续 7 位，故若设连续 7 位构成一个终极魔法的概率为 P，最终答案就是 E=(N-6)P。

我们只需要求 P，由分布的平均性，进而只需要计算前 7 位构成终极魔法的概率。这可以这么计算：

故

P=\dfrac{7!\times a_1\times a_2\times \cdots a_7}{N(N-1)\cdots(N-6)}

于是最终的答案是

E=(N-6)P=\dfrac{7!\times a_1\times a_2\times \cdots a_7}{N(N-1)\cdots(N-5)}

时间复杂度 \Theta(1)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
double a[8],ans;
int main(){
    for(int i=1;i<=7;i++)
        cin>>a[i],n+=a[i];
    ans=a[1]*1.0/n*a[2]/(n-1)*a[3]/(n-2)*a[4]/(n-3)*a[5]/(n-4)*a[6]/(n-5)*a[7]*5040;
    //7!=5040
    printf("%.3f",ans);
    return 0;
}