题目描述

　　有\(1\sim n\)一共\(n\)个数。保证\(n\)为偶数。

　　你要把这\(2n\)个数两两配对，一共配成\(n\)对。每一对的权值是他们两个数的和。

　　你想要知道这\(n\)对里最大的权值的期望是多少。

　　请输出答案对\(1000000007\)取模的值。

　　\(n\leq 500000\)

题解

　　枚举\(v\)，计算最大权值\(\leq v\)的概率。

　　从大到小枚举\(> \frac{v}{2}\)的数，这些数每次都有\(v-n\)种选择，方案数为

　　\(\leq \frac{v}{2}\)的数可以随便匹配。

　　记\(f(x)\)为\(x\)个数随便匹配的方案数，那么

　　（考虑\(x\)的全排列，\(a_{2i-1}\)和\(a_{2i}\)匹配。）

　　时间复杂度：\(O(n\log n)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll p=1000000007;

ll fp(ll a,ll b)

{

	ll s=1;

	for(;b;b>>=1,a=a*a%p)

		if(b&1)

			s=s*a%p;

	return s;

}

ll f[500010];

ll g[1000010];

int main()

{

#ifndef ONLINE_JUDGE

	freopen("b.in","r",stdin);

	freopen("b.out","w",stdout);

#endif

	int n;

	scanf("%d",&n);

	ll ans=0;

	f[0]=1;

	for(int i=2;i<=n;i+=2)

		f[i]=f[i-2]*(i-1)%p;

	for(int i=n+1;i<=2*n;i++)

		g[i]=fp(i-n,n-i/2)*f[n-2*(n-i/2)]%p;

	for(int i=2*n;i>=n+1;i--)

		g[i]=(g[i]-g[i-1])%p;

	for(int i=n+1;i<=2*n;i++)

		ans=(ans+g[i]*i)%p;

	ans=ans*fp(f[n],p-2)%p;

	ans=(ans+p)%p;

	printf("%lld\n",ans);

	return 0;

}