这个题数据范围较大,我没看到数据,想直接来一发莫队(好傻的想法)。
很明显,不能直接暴力,我们需要一个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; }