生涯回忆录

链接：https://ac.nowcoder.com/acm/contest/9033/C
求a的所有子集的mex之和
思路：虽然a[i]到1e9，但这n个数的任意子集的mex只会是1到n+1的一个数，因此从1到n+1枚举每个数作为mex的情况即可。一个数i作为mex，显然1~i-1的数都要每个至少选一个，大于i的数随便选
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10, mod = 20000311;
ll q_pow(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 n;
unordered_map<int,int> mp;
int main()
{
    scanf("%d",&n);
    for(int i=1,x; i<=n; i++){
        scanf("%d",&x);
        mp[x]++;
    }
    ll ans = 0, l = 1, cnt = n;
    for(int i=1; i<=n+1; i++){
        cnt -= mp[i];
        ans = (ans + q_pow(2, cnt) * l % mod * i % mod) % mod;
        l = l * (q_pow(2, mp[i]) - 1) % mod;    //每个数的mp都分块了，方便处理
    }
    printf("%lld\n", ans);
}