Python3(3.9) 解法, 执行用时: 1483ms, 内存消耗: 73076K, 提交时间: 2020-11-28 13:35:25

mod = 20000311
n = int(input())
c = [0 for i in range(n+5)]
mp = list(map(int, input().split()))
for i in mp:
    if i <= n:
        c[i] += 1
    else :
        c[n+2] += 1
ksm = [1]
for i in range(1, n+3):
    ksm.append(ksm[i-1] * 2 % mod)
fac1 = [1]
for i in range(1, n+1):
    fac1.append(fac1[i-1] * (ksm[c[i]] - 1) % mod)
fac2 = [1 for i in range(n+5)]
for i in range(n+2, 0, -1):
    fac2[i] = fac2[i+1] * ksm[c[i]] % mod
ans = 0
for i in range(1, n+2):
    ans += i * fac1[i-1] * fac2[i+1] % mod
    ans %= mod
print(ans)

C++(clang++11) 解法, 执行用时: 207ms, 内存消耗: 8940K, 提交时间: 2020-11-22 19:15:57

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,mod=20000311;
int n;
int a[N];
map<int,int> mp;
int pw[N];
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),mp[a[i]]++;
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2ll%mod;
	int pre=1,sum=0,ans=0;
	for(int i=1;i<=n+1;i++){
		sum+=mp[i];
		ans=(ans+(1ll*pre*pw[n-sum]%mod*i%mod))%mod;
		if(mp[i]==0) break;
		pre=1ll*pre*(pw[mp[i]]-1)%mod;
	}
	cout<<ans;
	return 0;
}