Poker

发表于 |
字数统计: 308 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※

Description

N张扑克（N为偶数），随机分配，分为N/2两堆，依次比较两堆中元素，第一队大，则A得分1，否则B的分1, 求A，B得分的期望,答案乘以N！

Solution

首先明白，因为答案乘以N！，所求则变为了方案数。因为每一个元素在每一个位置是等概率的，所以每一对元素都会给出贡献，求出即可。计算过程需要long long

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nn=100005;
const int mod=1e9+7;
int n,a[nn];ll les[nn],mor[nn];
ll ans=0,jc[nn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n); a[0]=0; a[n+1]=0x3f3f3f3f;
    for(int i=1,j=0;i<=n;i++){
        while(a[j+1]!=a[i]) ++j;
        les[i]=j;
    }
    for(int i=n,j=n+1;i>0;i--){
        while(a[j-1]!=a[i]) --j;
        mor[i]=n-j+1;
    }
    jc[0]=1; for(int i=1;i<=n;i++) jc[i]=(jc[i-1]*i)%mod;
    for(int i=1;i<=n;i++) ans=(ans+n/2*les[i]%mod*jc[n-2])%mod; printf("%lld ",ans); ans=0;
    for(int i=1;i<=n;i++) ans=(ans+n/2*(n-mor[i]-1)%mod*jc[n-2])%mod; printf("%lld\n",ans);
    return 0;
}