题意

给定一个集合，问它的所有子集里，最小的没出现过的正整数之和是多少。

solution

先桶一遍。因为只有个数，所以每个区间的贡献（也就是每个区间没出现过的最小正整数）的取值范围必定在。所以其实桶只需要统计范围内就可以了。

那么只需要遍历桶：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500010, mod = 20000311;
int n, cnt[N];
ll qkpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (x <= n) ++cnt[x];
    }
    ll p = 1, q = n, ans = 0;
    for (int i = 1; i <= n + 1; i++) {
        q -= cnt[i];  //剩下的点
        ans += p * qkpow(2, q) % mod * i, ans %= mod;
        //加上所有不选值为i的点的区间的贡献
        //剩下的每个点选或不选，所有的方案情况总数就是2**n
        // i是价值 aka“遗憾”
        p *= (qkpow(2, cnt[i]) - 1), p %= mod;  //选上该点的所有区间数量
        //不能不选，不能让它为空集
    }
    printf("%lld", ans);
    return 0;
}