题解：CF959F Mahmoud and Ehab and yet another xor task

· · 题解

CF959F Mahmoud and Ehab and yet another xor task

默认读者已学习过线性基

记目前操作到了 i，都进行了线性基的 insert 操作，记 i 前已有 cnt 个 a_i 可被表示出来，lb_i 为线性基中最高位 1 为 i 的基，s(x) 为可构成 x 的基的集合（例如：s(x)=\{lb_1,lb_2,lb_4\}，说明 x=lb_1 \oplus lb_2 \oplus lb_4），根据线性基的特性，一个可表示的数的构成方法唯一。

记 i 之前可被表示的数为 x_1,x_2,...,x_{cnt}，若当前查询的 x 可被表示，那么 x 的表示集合可概括为 \{s(x),(x_1,s(x_1)),(x_2,s(x_2)),..., (x_k,s(x_k))\}，这里当然可能出现重复，但这只是概括形式，无伤大雅。为什么构成集合中可能出现 x_i,s(x_i)？因为对于任意 1\le i \le cnt，有 x_i \oplus s(x_i)=0，那么这对对异或和的贡献可以通过同时选择 x_i 与 s(x_i) 消除。

综上来看，异或和 =x 的构成集合可看作 \{s(x) ,(x_1,x_2,...,x_k),(lb_1,lb_2,...,lb_p)\}（这里依然可能重复，只是表示形式），后面的 (lb_1,lb_2,...,lb_p) 是前面所选择的 x_1,x_2,...,x_k 的所有 s(x_1),s(x_2),...,s(x_k) 异或起来化简的集合，有 (x_1 \oplus x_2 \oplus...\oplus x_k) \oplus (lb_1 \oplus lb_2 \oplus ...\oplus lb_p)=0，这对整体的异或答案无影响，结果始终为 x。那么对于一对 (x_i,s(x_i))，其在 x 的构成集合中有两种状态——同时存在或不存在，那么对于所有可被表示的数，与其表示集合，便有答案为 2^{cnt}，cnt 为 i 前可被基表示出来的数的个数，那么可以记 sz 为目前线性基中非 0 基的个数，在插入新基时累加，那么有答案为 2^{i-sz}，具体实现将 l 离线下来查询即可。

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
using namespace std;
const int Maxn=1e5+5;
const int Mod=1e9+7;
int n,q,cnt,a[Maxn],lb[40],f[Maxn],ans[Maxn];
vector<pii> e[Maxn];
void insert(int x)
{
    for(int i=31;i>=0;i--)
    {
        if(x>>i&1) 
        {
            if(!lb[i]) 
            {
                lb[i]=x;
                cnt++;
                return ;
            }
            x=(lb[i]^x);
        }
    }
}
bool check(int x)
{
    for(int i=31;i>=0;i--)
    {
        if(x>>i&1) x=(x^lb[i]);
    }
    return x==0;
}
signed main()
{
    cin>>n>>q;
    f[0]=1;
    for(int i=1;i<=n;i++) f[i]=f[i-1]*2%Mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=q;i++)
    {
        int l,x;cin>>l>>x;
        e[l].push_back({x,i});
    }
    for(int i=1;i<=n;i++)
    {
        insert(a[i]);
        for(auto p:e[i])
        {
            int x=p.first,id=p.second;
            if(check(x)) ans[id]=f[i-cnt];
        }
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}