题目链接

简要题意：给定一个集合，求集合里面每一个子集的 MEX。

这里定义一个集合的 MEX 为这个集合最小的没有出现的数

考虑一个数作为 MEX 在几个子集里面出现，首先它能成为 MEX 需要小于它的自然数都至少出现一个，也就是它必须小于等于给定的集合的 MEX。

枚举每一个 MEX，记录每个可能称为 MEX 的数 的出现次数 ，那么对与小于当前 MEX 的数先减去必须选的那一个数，然后乘法原理乘起来子集个数，再乘上大于当前 MEX 的数的子集个数就是当前 MEX 的出现次数，枚举到的每一个 MEX 贡献的答案加起来即可。

时间复杂度 ，枚举 MEX ，其中有个快速幂的 。

//Code by do_while_true
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define re register
#define int long long
const int mod = 20000311;
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? ~x + 1 : x; }
inline int read() {
    int r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        r = (r << 3) + (r << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? ~r + 1 : r;
}
int qpow(int x, int y) {
    if(y <= 0) return 1;
    x %= mod; int sumq = 1;
    while(y) {
        if(y & 1) sumq = sumq * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return sumq;
}
#undef int
const int N = 500010;
int n, a[N], cnt[N];
ll ans;
signed main() {
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    std::sort(a + 1, a + n + 1);
    int up = 0;
    for(int i = 1; i <= n; ++i) {
        if(a[i] <= n) ++cnt[a[i]];
        if(a[i] == up + 1) up = a[i];
    }
    ll sum = 1, ssum = 0;
    for(int i = 1; i <= up + 1; ++i) {
        ssum += cnt[i];
        (ans += i * (sum * qpow(2, n - ssum)) % mod) %= mod;
         sum = (sum * ((qpow(2, cnt[i]) - 1 + mod) % mod)) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}