【XSY2786】Mythological VI 数学

题目描述

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

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

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

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

　　\(n\leq 500000\)

题解

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

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

\[{(v-n)}^{n-\frac{v}{2}}
\]

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

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

\[f(x)=\frac{x!}{2^{\frac{x}{2}}(\frac{x}{2})!}
\]

　　（考虑\(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;
}