Linear basis property function code to achieve 3000 words detailed explanation, with examples

Catalog

Linear basis properties

Linear basis construction

Find the maximum value of sequence XOR based on linear basis

Find the minimum XOR of linear basis

Linear basis to find the existence of an exclusive or value of the original sequence

The linear basis finds the K Minor difference or value

Example 1

Example 2

Example 3  

Example 4

---

Linear basis properties

1 Any number in the original sequence can be obtained by some number XOR in the linear base

2 Linear basis can represent 0 outside , All XOR results of the original sequence

3 Linear base XOR does not appear 0, This property is not determined by the original sequence , Even if the original sequence has XOR 0 Results appear , But linear bases don't

4 Once the linear basis is determined , Is the only

5 The number of linear base XOR results is   (1<<cnt)  

Linear basis construction

void add(ll x)
{
    for(ll i=60; i>=0; i--)
    {
        if(!(x&(1ll<<i)))
        {
           if(!p[i])
            {
                p[i]=x;
                
                break;
                
            }
            else
                x^=p[i];
            
        }
    }
}

Find the maximum value of sequence XOR based on linear basis

ll getmax(ll x)
{
   ll ans=0;
   
   for(ll i=60;i>=0;i--)
   {
       if((ans^p[i])>ans)
       {
           ans^=p[i];
           
       }
   }
   
   return ans;
   
}

Find the minimum XOR of linear basis

Because the original sequence is slightly different from the linear base XOR minimum , So you need to pay attention .

Linear basis to find the existence of an exclusive or value of the original sequence

bool check(ll y)
{
    for(int i=35;i>=0;i--)
    {
        if(y&(1ll<<i))
        {
            y^=x[i];

        }
    }

    return y==0;


}

The linear basis finds the K Minor difference or value

There are three steps

One , Reconstruct linear basis , Linear basis has i When a , For less than i All places of bits are exclusive or p[j]

Obtain the non-zero reconstructed linear basis and its number

Two , Judge whether the XOR result of the original sequence is 0 Of , If there is ,k-1

3、 ... and , Binary decomposition k, If k be not in 0--(1<<cnt)-1 within , There is no solution.

otherwise , If k Binary system i Who is on the 1, Then the result XOR reconstructs the linear basis

ll rebuild()
{
    int cnt=0;
    
    for(ll i=62;i>=0;i--)
    {
        for(ll j=i-1;j>=0;j--)
        {
            if(p[i]&(1ll<<j))
                p[i]^=p[j];
            
        }
    }
    
    for(ll i=0;i<=62;i++)
    {
        if(p[i])
            d[cnt++]=p[i];
        
    }
}


ll kth(int k)
{
    if(k>=(1ll<<cnt))
        return -1;
    
    
    ll ans=0;
    
    for(int i=62;i>=0;i--)
    {
        if(k&(1ll<<i))
            ans^=d[i];
        
    }
    
    return ans;
    
}

Example 1

【 Templates 】 Linear base - Luogu

Investigate the maximum query

#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
# include<set>
#include <iostream>
using namespace std;
typedef  long long int   ll;

ll a[110];

ll p[100];

void get(ll x)
{
    for(ll i=62;i>=0;i--)
    {
        if(!(x&(1ll<<i)))
            continue;

        if(!p[i])
        {
            p[i]=x;

            break;

        }

        x^=p[i];

    }
}
int main()
{


    ll n;

    cin>>n;

    ll ans=0;


    for(int i=1;i<=n;i++)
    {
        cin>>a[i];

        get(a[i]);

    }


    for(ll i=62;i>=0;i--)
    {
        if(ans<(ans^p[i]))
        {
            ans=ans^p[i];

        }
    }

    cout<<ans;


    return 0;
}

Example 2

Examine the judgment of the existing situation

xor Sequence

 

#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
# include<set>
#include <iostream>
using namespace std;
typedef  long long int   ll;

ll a[100000+10];
ll x[50];


void get(ll y)
{
    for(ll i=35;i>=0;i--)
    {
        if(!(y&(1ll<<i)))
            continue;

        if(x[i]==0)
        {
            x[i]=y;

            break;

        }
        else
            y^=x[i];
    }
}

bool check(ll y)
{
    for(int i=35;i>=0;i--)
    {
        if(y&(1ll<<i))
        {
            y^=x[i];

        }
    }

    return y==0;


}
int main()
{


       int n;

       cin>>n;

       for(int i=1;i<=n;i++)
       {
           cin>>a[i];

           get(a[i]);

       }

       int t;

       cin>>t;

       while(t--)
       {
           ll aa,bb;

           cin>>aa>>bb;

           bb^=aa;

           if(check(bb))
           {
               cout<<"YES"<<'\n';

           }
           else
           {
               cout<<"NO"<<'\n';

           }
       }



    return 0;
}

Example 3  

[TJOI2008] coloured lights - Luogu

We regard the switch as the original sequence , And the opening and closing of the lamp is the result of its binary decomposition , The result of exclusive or of two or more switches is the final opening and closing of the lamp , Express all results with linear basis , Investigation nature 5

#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
# include<set>
#include <iostream>
using namespace std;
typedef  long long int   ll;


ll p[100];

void get(ll x)
{

    for(int i=62;i>=0;i--)
    {
        if(!(x&(1ll<<i)))
            continue;

        if(p[i]==0)
        {
            p[i]=x;

            break;
        }
        else
        {
            x^=p[i];

        }
    }
}
int main()
{

      ll n,m;

      cin>>n>>m;


      for(int i=1;i<=m;i++)
      {
          string s;

          cin>>s;

          ll now=0;

          for(int j=0;j<s.length();j++)
          {
              if(s[j]=='O')
                now|=(1ll<<j);

          }

          get(now);

      }

      ll cnt=0;

      for(int i=0;i<=62;i++)
      {
          cnt+=(p[i]!=0);
      }

      ll ans=1;
      for(int i=1;i<=cnt;i++)
      {
          ans=ans*2%2008;

      }
      cout<<ans;

    return 0;
}

Example 4

(Zero XOR Subset)-less

Investigation nature 2,3. According to the meaning , We found that an XOR sub segment can be obtained by the difference or difference of prefix XOR array , So the linear basis can record all n The XOR condition of an XOR prefix array , nature 2 It ensures that they cannot exist XOR, and the result is 0 The situation of , nature 3 It ensures that the XOR values of these sub segments can be represented . And it's worth noting that , If all n Number XOR is not followed by 0, Then our linear basis must be able to transform this n All the numbers are included , Then use this large prefix XOR value to “ decompose ” The remaining small . But if n The number XOR is followed by 0, Then at least this result does not satisfy the property that linear basis represents non-zero , Thus cannot be added , Unable to participate in cutting , The rightmost endpoint is no longer n

#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
# include<set>
#include <iostream>
using namespace std;
typedef  long long int   ll;

ll a[1000000];

ll p[100];

void get(ll x)
{
    for(ll i=62;i>=0;i--)
    {
        if(!(x&(1ll<<i)))
            continue;

        if(!p[i])
        {
            p[i]=x;

            break;

        }

        x^=p[i];

    }
}

int main()
{


    ll n;

    cin>>n;

    ll ans=0;


    ll now=0;


    for(int i=1;i<=n;i++)
    {
        cin>>a[i];

        now^=a[i];


        get(now);

    }


    int cnt=0;
    
    // There may be 0, But linear base XOR will not appear 0
    
    // If fn No 0, Then the linear basis can express fn Exclusive or all remaining values ,

    if(now==0)
    {
        cout<<-1;
        
        return 0;
        
    }
    for(ll i=62;i>=0;i--)
    {
        if(p[i])
        {
            cnt++;

        }
    }

    cout<<cnt;


    return 0;
}

XOR set of