qboimathtest1 t2 配对-白红宇

qboimathtest1 t2 配对

阅读量：6268 次

发布时间：2019-06-22

本文共 1023 字，大约阅读时间需要 3 分钟。

题目

有1~n一共n个数，n为偶数。小Q要把这n个数随机地两两配对。令每一对的权值为它们两个数的和。小Q想要知道这n/2对里最大的权值的期望是多少。请输出答案对10^9+7取模的值。

【输入】

一行一个正整数 N。

【输出】

一行一个整数，表示答案对10^9+7取模的值。

【输入样例】

【输出样例】

对于 20%的数据： 1 ≤ N ≤ 10。

对于 40%的数据： 1 ≤ N ≤ 2000。

对于 100%的数据： 1 ≤ N ≤500000。

分析

见

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const long long mod=1e9+7;long long c[1100000];inline long long pw(long long a,long long p){a%=mod;long long res=1;while(p){if(p&1)res=res*a%mod;a=a*a%mod;p/=2;}return res;}int main(){long long n,m,i,j,k,v,ans=0,be=0;scanf("%lld",&n);c[0]=1;for(i=1;i<=n/2;i++)c[i]=c[i-1]*(i*2-1)%mod;v=2*n-1;for(i=n+1;i<=v;i++){long long low=(2*n-i+1)/2;long long now=pw(i-n,low)%mod*c[n/2-low]%mod;ans=(ans+(now-be+mod)%mod*i%mod)%mod;be=now;}ans=ans*pw(c[n/2],mod-2)%mod;cout<
                   
                    <