CF959F题解

傅天宇 · 2020-05-31 17:08:02 · 题解

前言：

萌新最近刚刚学了线性基，而且这道题昨天卡了一天，就写篇题解巩固下。由于我非常的懒，不想码2遍，所以模板的题解就跟这道题一起发在这里吧。

开始正文：

嗯，首先，什么是 线性基 ？

百度百科：线性基是竞赛中常用来解决子集异或一类题目的算法。

OI WiKi：线性基是向量空间的一组基，通常可以解决有关异或的一些题目。

通俗一点，就是由一个集合构造出来的另一个集合。（

它有何作用呢？

维护异或和。

它有什么性质呢？

线性基的元素能相互异或能还原原序列，且它是满足此性质的最小的集合。
线性基里没有异或和为 0 的子集。
线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
线性基中每个元素的二进制最高位互不相同。

——对 OI WiKi 所说的进行了适当改编。

你说了这么多了，那原集合是怎么得到线性基的集合呢？

放个代码，更容易理解~。

#define M 25  //根据题意给出的样例范围，此题为25,(然而开大了也没事。
void get_xxj(int x)
{
    for(re i=M;i>=0;i--)
    {
        if(x&1<<i)//M>=30时就要写(x&1ll<<i)了。
        {
            if(xxj[i]) x^=xxj[i];
            else 
            {
                xxj[i]=x;//如果xxj[i]为0，则为x之前被异或后的数字。
                break;
            }
        }
    }
}

明显地看到一个个地插入，最终得到线性基的集合。

由此，我们又可以改编一下，写成如下的代码，判断是否可以成功插入。

如果可以，则干啥；

不可以，则干啥。

#define M 25  
bool check(int x)
{
    for(re i=M;i>=0;i--)
    {
        if(x&1<<i)
        {
            if(xxj[i]) x^=xxj[i];
            else return 0;//成功插入。
        }
    }
    return 1;//这个数已经可以被其他数异或得到，就不用插了。
}

好的，现在我们来看这道题。

题意：询问前 cnt 个数字中有多少个子集异或起来等于 x 。

先预处理出 lg 数组，按照 l 排序，然后插入，判断 x ，如果可以被线性基的集合求出，设 tot 是此时的线性基的集合内没有用到的数，答案就是 2^{cnt-tot} ，很好理解。

也没啥核心代码，就放整个的吧。

#include<bits/stdc++.h>
using namespace std;
//省略50行的火车头。
#define re register int//卡常是个好习惯呢。
#define N 100005
#define M 25//根据题意改M大小，题目是2^20，就写25吧。
const int mod=1e9+7;//mod模数。

inline int read()//快读，卡常是个好习惯呢。
{
    int x=0;
    bool flag=true;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') flag=false;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    if(flag) return x;
    return ~(x-1);
}

int n,q,tot,cnt;//上文说的tot,cnt和题意的n,q。
int a[N],lg[N],ans[N];//初始的子集,log数组,答案数组。

struct node
{
    int l,x,id;
    bool operator < (const node &a) const 
    {
        if(l!=a.l) return l<a.l;
        return x<a.x;
    }
}b[N];//结构体+排序。

int xxj[M+5];//线性基的子集。

void get_xxj(int x)
{
    for(re i=M;i>=0;i--)
    {
        if(x&1<<i)
        {
            if(xxj[i]) x^=xxj[i];
            else 
            {
                xxj[i]=x;
                tot++;
                break;
            }
        }
    }
}//上文说的，插入线性基子集。

bool check(int x)
{
    for(re i=M;i>=0;i--)
    {
        if(x&1<<i)
        {
            if(xxj[i]) x^=xxj[i];
            else return 0;
        }
    }
    return 1;
}//上文已说。

int main()
{
    n=read();
    q=read();
    for(re i=1;i<=n;i++) a[i]=read();
    for(re i=1;i<=q;i++)
    {
        b[i].l=read();b[i].x=read();
        b[i].id=i;
    }//读入,卡常是个好习惯呢。
    lg[0]=1;
    for(re i=1;i<=n;i++) lg[i]=(lg[i-1]<<1)%mod; //预处理lg数组。 
    sort(b+1,b+1+q);//排序。
    for(re i=1;i<=q;i++)
    {
        while(cnt<b[i].l) get_xxj(a[++cnt]);
        if(check(b[i].x)) ans[b[i].id]=lg[cnt-tot];
    }

前文已说：

如果可以被线性基的集合求出，tot 是此时的线性基的集合内没有用到的数，答案就是 2^{cnt-tot} ，很好理解。

    for(re i=1;i<=q;i++) cout<<ans[i]<<endl; //输出答案。
    return 0;//完结撒花。
}

顺便再安利一下我的博客 \ \