题意

求出所以子集中最小没有出现的正整数之和。

分析

我们可以考虑一个元素的贡献，我们先考虑如果这个数 可以作为答案，那么 的每个元素至少选取了一次。那么根据乘法原理， 的总方案为 。 表示 这个数出现的次数。那么 的元素，可以选也可以不选总的方案数为 。上面的指数也可以通过前缀和维护。那么当元素的取值不连续时，我们就可以退出了，因为无论怎么选，答案都不能比这个大了。由于是考场写的，有点丑。

代码

//  sto xzc orz
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 5e5 + 1000,mod = 20000311;
int ksm(int a,int b) {
    int x = 1;for(;b;b >>= 1,a = a * 1ll * a % mod) {
        if(b & 1) x = x * 1ll * a % mod;
    }return x;
}
int A[N],n,B[N],C[N],fac[N],ifac[N],tot,M = 5e5;
int main() {
    n = read();
    for(int i = 1;i <= n;i++) A[i] = B[i] = read();
    sort(B+1,B+1+n);
    tot = unique(B + 1,B + 1 + n) - B - 1;
    for(int i = 1;i <= n;i++) if(A[i] <= M) C[A[i]]++;
    int ans = 0,L = 1,res = 0;
    for(int i = 1;;i++) {
        auto it = lower_bound(B + 1,B + 1 + tot,i);
        if((*it) != i) {ans = (ans + (L *1ll* ksm(2,n - res)%mod * 1ll * i % mod)) % mod;break;}
        else ans = (ans + (L *1ll* ksm(2,n - res - C[i])%mod * 1ll * i % mod)) % mod;
        L = (L * 1ll * ((ksm(2,C[i])) - 1 + mod)% mod ) % mod;
        res += C[i];
    }
    cout << ans << endl;
    return 0;
}