考虑算每一个位置在所有情况的期望值乘以全排列似乎就是答案.
那么对于 $i$，如果要由 $j$ 来贡献的话就要满足 $j$ 在 $i....j-1$ 之前先拿.
而在拿 $j$ 时，先于 $i...j-1$ 的概率就是 $\frac{1}{|j-i|+1}$
直接对所有的 $j$ 加和，然后乘以个概率即可.
code:
#include <bits/stdc++.h>
#define LL long long
#define N 100005
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const LL mod=1000000007;
LL a[N],n,inv[N],sum[N];
LL fac(int p)
{
LL ans=1ll;
for(int i=2;i<=n;++i) ans=ans*1ll*i%mod;
return ans;
}
int main()
{
// setIO("input");
int i,j;
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%lld",&a[i]);
sum[1]=inv[1]=1ll;
for(i=2;i<=n;++i)
{
inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
sum[i]=(sum[i-1]+inv[i])%mod;
}
LL ans=0ll;
for(i=1;i<=n;++i)
{
ans=(ans+a[i]*((sum[i]-sum[0]+sum[n-i+1]-sum[1]+mod)%mod)%mod)%mod;
}
printf("%lld\n",ans*fac(n)%mod);
return 0;
}
[AGC028B]Removing Blocks 概率与期望
原文：https://www.cnblogs.com/guangheli/p/11756292.html