2019牛客暑期多校训练营（第一场）：XOR（线性基）

题意：给定数组，求所有异或起来为0的集和的大小之和。

思路：由于是集合大小，我们换成考虑每个元素在多少个集合里有贡献。先生成线性基。

对于没有插入线性基的元素x，贡献是2^(N-base-1)，因为x选择之后，其他非基元素无论选还是不选，都可以调整基来使得异或和为0。

对于插入线性基的元素x，我们也同样这样考虑，把除了它的N-1个数生成线性基。就可以同样算贡献了。这里现在可以稍加优化，把最开始的非基元素预处理成一个线性基，这样生成新的线性基就快起来了。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep2(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

const int maxn=;

const int Mod=1e9+;

ll a[maxn],b[maxn],c[maxn],used[maxn]; int tot;

int qpow(int a,int x){

    int res=; while(x){

        if(x&) res=1LL*res*a%Mod;

        x>>=; a=1LL*a*a%Mod;

    } return res;

}

bool add(ll x,ll base[])

{

    rep2(i,,) {

        if(x&(1LL<<i)){

            if(!base[i]){ base[i]=x; return true;}

            x^=base[i];

        }

    }

    return false;

}

int main()

{

    int N,ans=;  ll x;

    while(~scanf("%d",&N)){

       rep(i,,) a[i]=b[i]=c[i]=; tot=;

       rep(i,,N) {

          scanf("%lld",&x);

          if(add(x,a)) used[++tot]=x;

          else add(x,b);

       }

       if(tot<N) ans=1LL*qpow(,N-tot-)*(N-tot)%Mod;

       rep(i,,tot){

           rep(j,,) c[j]=b[j];

           rep(j,,tot) if(i!=j) add(used[j],c);

           if(!add(used[i],c)) (ans+=qpow(,N-tot-))%=Mod;

       }

       printf("%d\n",ans);

    }

    return ;

}

巴特西

2019牛客暑期多校训练营（第一场）：XOR（线性基）

最新文章

热门文章