51Nod1309 Value of all Permutations 期望

​題目傳送門 - 51Nod1309​​

題意

長度為N的整數數組A，有Q個查詢，每個查詢包含一個數M，對A的所有不同排列，執行find函數（需用到查詢中的M），你來計算find函數的傳回值的和。由于結果很大，輸出Mod 1000000007的結果。

void find(int permutation_A[], int M){
    x = Length(permutation_A);
    sum = 0;
    for(i = 0; i < x; i++) {
        if (permutation_A[i] <= M)
            sum = sum + permutation_A[i];
        else
            break;
    }
    return sum;
}      

題解

　　我們首先考慮求答案的期望。

　　由于期望具有線性性，是以我們可以對于每一個數字對答案的貢獻分開考慮。

　　顯然，如果在一個排列中，如果目前數字産生貢獻，當且僅當該數字不大于 m ，且所有大于 m 的數字都出現在它後面。那麼，設大于等于 m 的數字有 k 個，假設目前數字不大于 m ，那麼目前數字産生貢獻的機率是 $\frac{1}{k+1}$ 。那麼它對總期望的貢獻就是 它的值 × 機率。我們隻需要把所有不大于 m 的數對期望的貢獻求和就可以得到總期望了。又由于，所有不大于 m 的數産生貢獻的機率相同，是以我們可以字首和處理一下，快速求得期望。

　　是以最終答案就是期望 × 排列總數。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=50005,mod=1e9+7;
int n,q,a[N],Ha[N],p[N],hs;
int Fac[N];
int Pow(int x,int y){
  int ans=1;
  for (;y;y>>=1,x=1LL*x*x%mod)
    if (y&1)
      ans=1LL*ans*x%mod;
  return ans;
}
int main(){
  scanf("%d%d",&n,&q);
  for (int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  sort(a+1,a+n+1);
  for (int i=1;i<=n;i++)
    Ha[i]=a[i];
  hs=1;
  for (int i=2;i<=n;i++)
    if (Ha[i]!=Ha[i-1])
      p[hs]=i-1,Ha[++hs]=Ha[i];
  p[hs]=n;
  for (int i=1;i<=n;i++)
    a[i]=(a[i-1]+a[i])%mod;
  Fac[0]=1;
  for (int i=1;i<=n;i++)
    Fac[i]=1LL*Fac[i-1]*i%mod;
  int ans=Fac[n];
  for (int i=1;i<=hs;i++)
    ans=1LL*ans*Pow(Fac[p[i]-p[i-1]],mod-2)%mod;
  while (q--){
    int v;
    scanf("%d",&v);
    int x=upper_bound(Ha+1,Ha+hs+1,v)-Ha-1;
    int now=1LL*ans*Pow(n-p[x]+1,mod-2)%mod*a[p[x]]%mod;
    printf("%d\n",now);
  }
  return 0;
}