小魔女帕琪

小魔女帕琪

有\(a_1,a_2,...,a_7\)个对应的\(1,2,...,7\)进行排列，询问其中出现\(1,2,...,7\)的全排列的个数的期望，a1+a2+a3+a4+a5+a6+a7<=10^9。

解

显然数据范围不支持递推方程，于是猜测为条件概率问题，即前后概率发生有联系，通常相等，于是设其中一个状态，不妨设在第n个位置到最后一个位置，出现了一次1234567的全排列期望，为（设此时有12..7,\(a_1,...,a_7\)个,其和为n）

\[\frac{7!\prod_{i=1}^7a_i}{\prod_{i=1}^7(n-i+1)}\]

在考虑n+1个位置出现全排列的期望，不难得知有

\[\frac{7!(a_1-1)\prod_{i=1}^7a_i}{\prod_{i=1}^7(n-i+1)}\]
\[\frac{7!(a_2-1)\prod_{i=1}^7a_i}{\prod_{i=1}^7(n-i+1)}\]
\[....\]

累加我们有

\[\frac{7!(a_1-1+a_2-1+...+a_7-1)\prod_{i=1}^7a_i}{\prod_{i=1}^7(n-i+1)}=\]

\[\frac{7!\prod_{i=1}^7a_i}{\prod_{i=1}^7(n-i+1)}\]

于是我们得知任何一个位置到终点的期望与下一个位置到终点的期望都相同，根据数学归纳法，当然递归更好理解，于是我们得知任何一个地方出现全排列概率都是相同的。

于是

\[ans=\frac{7!\prod_{i=1}^7a_i}{\prod_{i=1}^7(n-i+1)}(n-7+1)=\]

\[\frac{7!\prod_{i=1}^7a_i}{\prod_{i=1}^6(n-i+1)}\]

代入式子计算即可。

参考代码：

#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
double a[7];
int main(){
    ri int i,n(0);double ans(1);
    for(i=0;i<7;++i)
        scanf("%lf",&a[i]),n+=a[i];
    for(i=0;i<6;++i)
        ans*=a[i],ans*=(i+1),ans/=(n-i);
    ans*=a[i],ans*=(i+1);
    printf("%.3lf",ans);
    return 0;
}

小魔女帕琪

原文：https://www.cnblogs.com/a1b3c7d9/p/10818951.html