利用斯特林数转下降幂的技巧，再求期望。
单纯求 $x^3$ 的期望比较简单，两次差分即可。考虑加强一下，求 $x^m$ 的期望。用二项式定理拆开求每一项可以做到 $\mathcal O(nm^2)$。
还能做到更优吗？我们发现直接求 $x^m$ 的期望是非常困难的。考虑拆开，但不是用二项式定理，而是利用斯特林数转下降幂的技巧：
对于每个 $k$ 求 $x^{\underline k}$ 的期望最后乘上系数得到答案。时间复杂度 $\mathcal O(m^2+nm)$。
实际上，还有一种办法避免求逆元，将 $x^{\underline k}$ 转化为 $k!\binom{x}{k}$，即求 $\binom{x}{k}$ 的期望。过程中可以根据 $\binom{x}{k}=\binom {x-1}{k-1}+\binom{x-1}{k}$ 直接递推即可（二者本质上是一样的）。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,M=10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
double p,a[N],b[N];
int fac[M],s[N][M];
int main()
{
read(n);
m=3;
fac[0]=1;
for(int i=1;i<=m;i++)fac[i]=fac[i-1]*i;
s[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=i;j++)
s[i][j]=s[i-1][j-1]+j*s[i-1][j];
for(int i=1;i<=n;i++,b[1]+=(a[1]=p))
{
scanf("%lf",&p);
for(int j=m;j>1;j--)a[j]+=a[j-1],a[j]*=p,b[j]+=a[j];
}
double ans=0;
for(int i=1;i<=m;i++)ans+=b[i]*fac[i]*s[m][i];
printf("%.1lf",ans);
return 0;
}
|