原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1309.html
题目传送门 - 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 ",now); } return 0; }