题意:
容斥二进制意义下至少哪些位置不相等。 #include#include #include #include #include #include #include #include #include #define N 2200000#define L 2000000#define eps 1e-7#define inf 1e9+7#define db double#define ll long long#define ldb long doubleusing namespace std;inline ll read(){ char ch=0; ll x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag;}const ll mo=998244353;ll ksm(ll x,ll k){ ll ans=1; while(k) { if(k&1)ans=ans*x%mo; k>>=1; x=x*x%mo; } return ans;}ll a[N],f[N],mi[N];int main(){ ll n=read(),ans; mi[0]=1; for(ll i=1;i<=n;i++)a[i]=read(),mi[i]=(mi[i-1]*2)%mo; for(ll i=1;i<=(1<<20)-1;i++)f[i]=f[i>>1]+(i&1); ans=mi[n]-2;ans=(ans*ksm(2,mo-2))%mo; for(ll s=0;s<=(1<<20)-1;s++) { ll cnt=0; for(ll i=1;i<=n;i++)if(s==(a[i]&s))cnt++; if(cnt==0||cnt==n)continue; if(f[s]&1)ans=(ans-(mi[cnt]-1))%mo; else ans=(ans+(mi[cnt]-1))%mo; } printf("%lld",(ans%mo+mo)%mo); return 0;}