526互联

F. Mahmoud and Ehab and yet another xor task 线性基

发布时间 2023-09-13 22:09:24作者: 久远寺冇珠

Problem - F - Codeforces

 题意：给出一个长度为n的数组，然后给出q次询问。

对于每次询问，给出一个l和一个x，请你求出在[1,l]这个区间内，有多少个子序列是好的，好的的定义是这个子序列的异或和为x。

做法：考虑线性基，先离线处理询问，对其l排序。然后对于l，求该情况下的线性基。然后，我们在检测一下x能否被我们的线性基给搞出来，如果不行，答案就是0。

否则，答案就是2的(当前的元素个数减去线性基里元素的个数)次方。这个也蛮好理解的，就是对于一个线性基外的数，他有两种选择，线性基外的数选完了之后，对于线性基，总可以选出一组基底来，使其异或和为x。

不过这题感觉还不太严谨哦，我本以为要特殊考虑0的情况，但好像这题数据水了。

 

struct kkk{
    int idx,l;
    ll x,ans;
};
bool cmp1(kkk a,kkk b){
    return a.l<b.l;
}
bool cmp2(kkk a,kkk b){
    return a.idx<b.idx;
}


vector<ll>B;
void insert(ll x){
    for(auto &b:B)x=min(x,b^x);
    for(auto &b:B)b=min(b,x^b);
    if(x)B.push_back(x);
}
bool check(ll x){
    for(auto &b:B)x=min(x,b^x);
    if(x)return false;return true;
}
void solve(){
    int n,q;cin>>n>>q;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<kkk>b(q+1);
    for(int i=1;i<=q;i++){
        cin>>b[i].l>>b[i].x;
        b[i].idx=i;
    }
    sort(b.begin()+1,b.end(),cmp1);
    int lt=0;
    for(int i=1;i<=q;i++){
        while(lt<b[i].l){
            lt++;insert(a[lt]);
        }
        if(check(b[i].x))b[i].ans=binpow(2ll,(ll)(lt-(LL)B.size()),mod);
        else b[i].ans=0ll;
    }
    sort(b.begin()+1,b.end(),cmp2);
    for(int i=1;i<=q;i++){
        cout<<b[i].ans<<"\n";
    }