C++(clang++ 11.0.1) 解法, 执行用时: 7ms, 内存消耗: 448K, 提交时间: 2023-07-07 21:36:06

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[200001];
const int mod=1e9+7;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%mod*a%mod;
    a=a%mod*a%mod; b>>=1;
  }
  return r;
}
int inv(int x){
  return qpow(x,mod-2);
}
int com(int n,int m){
  if(m>n||m<0||n<0)return 0;
  return f[n]*inv(f[m]*f[n-m]%mod)%mod;
}
signed main(){
  ios::sync_with_stdio(false);
  int n,c; cin>>n; c=n;
  for(int i=f[0]=1;i<=n;i++)
    f[i]=f[i-1]*i%mod;
  map<int,int> m;
  for(int i=1;i<=n;i++){
    int x; cin>>x; m[x]++;
  }
  for(int i=2;i<=n;i++)
    for(auto [x,y]:m)
      if(y>=(i+1>>1)){
        for(int j=i+1>>1;j<=y;j++)
          (c+=com(y,j)*com(n-y,i-j)%mod)%=mod;
        if(~i&1)
          for(auto [x2,y2]:m){
            if(x==x2)break;
            (c+=mod-com(y,i>>1)*com(y2,i>>1)%mod)%=mod;
          }
      }
  cout<<c<<endl;
  return 0;
}

pypy3 解法, 执行用时: 132ms, 内存消耗: 26832K, 提交时间: 2023-07-07 20:36:56

import sys
input = lambda:sys.stdin.readline().strip()
M = lambda:map(int,input().split())
inf = float('inf')
from collections import Counter
mod = 10**9+7
n = int(input())
arr = [0]+list(M())
a = [1,1]+[0]*(n-1)
b = [1,1]+[0]*(n-1)
for i in range(2,n+1):
    a[i] = a[i - 1] * i%mod
    b[i] = pow(a[i],mod-2,mod)
f = lambda n,m:a[n]*b[m]*b[n - m]%mod
ans = 0;
k = Counter(arr)
for xx in k.items():
    x,y = xx[1],n-xx[1]
    for i in range(1,x+1):
        yy = f(x, i)
        for j in range(min(i,y)+1):
            ans = (ans+yy * f(y, j))%mod
    for yy in k.items():
        if yy[0] >= xx[0]:continue
        for i in range(1,min(x,yy[1])+1):
            ans = (ans-f(x,i)*f(yy[1],i))%mod
print(ans)