线性基算贡献——19牛客多校第一场H

小鱼儿 2023-10-11 09:10 19阅读 0赞

/* 给定数组a[],求有多少集合的异或值为0，将这些集合的大小之和求出来 对于每个数来说，如果除去这个数后数组里做出的线性基和这个数线性相关，那么这个数贡献就是2^(n-1-线性基的大小) 反之这个数和线性基线性无关，即数组里凑不出这个数来和其异或等于0，所以贡献就是0 由于做n次线性基很麻烦，所以简化问题，只需要先做出一个基，将数分成在基内和基外即可 首先做出一个线性基base，设其大小为r 然后分情况来讨论： 1.对于线性基外的每个数，其贡献是2^(n-r-1) 2.对于每个线性基内的数字ai，做一个除去ai的线性基base' 如果base'和ai线性相关，那么ai的贡献就是2^(n-r-1), 反之ai和base'线性无关，贡献是0 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long 
    #define maxn 100005
    #define mod 1000000007
    struct LB{
        ll b[66],r;
        void clear(){
        for(int i=60;i>=0;i--)b[i]=0;r=0;}
        void insert(ll x){
            for(int i=60;i>=0;i--)if(x>>i & 1){
                if(!b[i]){
                    b[i]=x;r++;break;
                }
                x^=b[i];
            }
        } 
        int check(ll x){
            for(int i=60;i>=0;i--)if(x>>i & 1){
                if(!b[i])return 1;
                x^=b[i];
            }
            return 0;
        } 
    }base,tmp,tmp2;
    ll n,a[maxn],flag[maxn],flag2[maxn];
    
    ll Pow(ll a,ll b){
        ll res=1;
        while(b){
            if(b%2)res=res*a%mod;
            b>>=1;a=a*a%mod;
        }
        return res;
    }
    
    int main(){
        while(scanf("%lld",&n)!=EOF){
            ll ans=0;
            memset(flag,0,sizeof flag);
            base.clear();tmp.clear();
            for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
            for(int i=1;i<=n;i++)
                if(base.check(a[i])){
                    base.insert(a[i]);
                    flag[i]=1;
                }
            //在base之外再做一个线性基 
            for(int i=1;i<=n;i++)
                if(!flag[i])tmp.insert(a[i]);
            
            ll P=Pow(2,n-base.r-1);
            
            for(int i=1;i<=n;i++)
                if(!flag[i])//在线性基base外 
                    ans=(ans+P)%mod;
                else {
        //在线性基内 
                    tmp2=tmp;
                    for(int j=1;j<=n;j++)
                        if(flag[j]&&j!=i)tmp2.insert(a[j]);    
                    if(tmp2.check(a[i])==0)
                        ans=(ans+P)%mod;
                }
            cout<<ans<<endl;
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11272116.html