(Zero XOR Subset)-less-线性基

题意：把n个数分成多个集合，要求不能有集合为空，最终不能有非空子集合异或值为0，尽可能划分的多一些。

思路：非法情况就只有 n个数异或为0，其他的情况集合个数就是线性基的内元素的个数。（因为有基就可以保证不为0，并且不可以再增加元素）

基类似极大线性无关组。已经是最大的了，不可以再多。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define maxn 234567

ll n,a[maxn],p[maxn],ss,ans;

void getj(ll x)

{

    for(int i=60; i>=0; i--)

    {

        if(!(x>>i))continue;

        if(p[i]==0)

        {

            p[i]=x;

            break;

        }

        else x^=p[i];

    }

    if(x!=0)ans++;

}

int main()

{

    scanf("%lld",&n);

    for(int i=1; i<=n; i++)

    {

        scanf("%lld",&a[i]);

        ss^=a[i];

        getj(a[i]);

    }

    if(ss==0)printf("-1\n");

    else printf("%lld\n",ans);

    return 0;

}

巴特西

(Zero XOR Subset)-less-线性基

最新文章

热门文章