按值找排名（由一个集合S的任意子集异或和的值形成的集合）

题：https://www.luogu.com.cn/problem/P4869

题意：给定集合S，由集合S的若干个子集异或和出来的值形成的集合，问x在此集合中排名多少（下标）

分析：将这x个数放到线性基里去，然后就按位，若当前位置不为0，则一定取到这一位，就能找到x在去重后的排名；

　　　接着就算重复的出现了几次，考虑没被算进来的数y，因为已经存放进去的数能通过异或来得到y,那么异或部分异或上y就为0;

　　　那么x^0=x，也就是说x至少可以出现2^(n-|B|)次，而线性基的任意子集异或只能唯一表示为一个数，也就说明x最多也出现2^(n-|B|)次；

　　　而0不在线性基中，所以在算rank的时候k不必减1；

注意：线性基的任意子集异或都能唯一算出原集合中任意子集的异或||0不在线性基中

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int M=30;
const int mod=10086;
struct LB{
    int a[M+2];
    vector<int>vec;
    void init(){
        vec.clear();
        for(int i=0;i<=M;i++) a[i]=0;
    }
    void Insert(int x){
        for(int i=M;i>=0;i--){
            if(!(x>>i)&1) continue;

            if(a[i]) x^=a[i];
            else{
                for(int j=0;j<i;j++) if((x>>j)&1) x^=a[j];
                for(int j=i+1;j<=M;j++) if((a[j]>>i)&1) a[j]^=x;

                a[i]=x;
                return ;
            }
        }
    }
    void getvec(){
        for(int i=0;i<=M;i++) if(a[i]) vec.pb(i);
    }
    int getsz(){ return (int)vec.size(); }
    int getrank(int k){
        int res=0;
        for(int i=0;i<vec.size();i++) if((k>>vec[i])&1) res|=(1<<i);
        return res;
    }
}lb;
int ksm(int a,int b){
    int t=1;
    while(b){
        if(b&1) t=t*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return t;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int x,i=1;i<=n;i++){
        scanf("%d",&x);
        lb.Insert(x);
    }
    lb.getvec();
    int x;
    scanf("%d",&x);
    int k=lb.getrank(x);
    printf("%d
",(k%mod*ksm(2,n-lb.getsz())%mod+1)%mod);
    return 0;
}