C生涯回忆录题解

这个题数据范围较大，我没看到数据，想直接来一发莫队（好傻的想法）。

很明显，不能直接暴力，我们需要一个O(nlogn)的算法。

这道题通过观察可得，它的任意子集的Mex(x)必定小于等于n+1。

如果不能枚举回忆，那么我们可以去枚举回忆值，正好是1——n+1，再加一个快速幂正好是(nlogn)的算法。

枚举回忆值，很明显分成了比这个数小的一部分，和比这个数大的一部分。

比这个数大的一部分很好求，就是集合2^p(p为大的一部分)，难道小的也是这样求吗？

如果真的是这样子求那么前面部分是1，2，3，枚举值是4，前面难道真的等于8，不是，前面只有取1，2，3时才是4。

我们就可以发现前面数字至少有一个，否则枚举值就不是这个子集Mex值。

所以我们要预处理，记录下每个数字出现了多少次。前面部分的值就是每个不同回忆数字的真子集相乘，后面就是比枚举值大的所有数字子集值，因为后面取不取没差，那么这道题目就做完了。

代码如下：

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define fo1(a,b) for(int a=0;a<b;++a)
#define fo2(a,b) for(int a=1;a<=b;++a)
#define lowbit(a) (a&(-a))
#define fir(a) a->first
#define sec(a) a->second
const int inf=0x3f3f3f3f;
const int maxn=5e5+5;
const int MOD=20000311;
const double eps=1e-8;
int n,a[maxn];
map <int,int> m;
map <int,bool> vis;
inline ll quickpower(ll a,ll b){
    ll ans=1,base=a;
    while(b){
    if(b&1)
    ans=ans*base%MOD;
    base=base*base%MOD;
    b/=2;
    }
    return ans%MOD;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),m[a[i]]++;
    ll ans=0;
    ll num=0;
    ll cnt=1;
    for(int i=1;i<=n+1;++i){
        num+=(ll)m[i];
        //cout<<num<<endl;
        ans=(ans+((cnt*i)%MOD*(quickpower(2,n-num)))%MOD)%MOD;
        cnt=(cnt*(quickpower(2,m[i])-1))%MOD; //每个数字的集合不能出现空集所以-1
        //cout<<cnt<<"*****"<<endl;
        //cout<<ans<<endl;
    }
    printf("%lld\n",ans);
    return 0;
}