BZOJ2844 albus就是要第一个出场

传送门

题目大意

给定一个含 n 个自然数的集合S,将 2S 中所有集合的所有元素的异或和从小到大排列(下标从 1 开始),求tar在其中第一次出现的下标(保证给出的数出现过),对 10086 取模.

1≤n≤105,ai≤109.

题解

首先 tar=0 的情况最好先特判掉.

然后我们要求的是从 S 中取若干元素(可以不取)异或和小于tar的方案数.

然后依旧照上一题的方法高斯消元求线性基.

我们记录一下消出来的 0 的个数,先不考虑它们.

然后从线性基中取出一些数,使得它们的异或和为tar,这个方案是唯一的.

然后我们枚举这些数中哪一个不取,那么比它小的数就可以随便取了.

最后再算上 0 也可以随便取.

复杂度大概是O(30n).

代码

#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bitset>
#include <complex>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
#define pb push_back
#define y1 kjfasiv
#define lowbit(x) (x&-x)
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> veci;
const int mod=,INF=,rx[]={-,,,},ry[]={,,,-};
const double pi=acos(-),eps=;
template<class T>void rd(T &res){
    res=;
    char c;
    while(c=getchar(),c<);
    do res=(res<<)+(res<<)+(c^);
        while(c=getchar(),c>);
}
template<class T>inline void Max(T &a,T b){
    if(b>a)a=b;
}
template<class T>inline void Min(T &a,T b){
    if(b<a)a=b;
}
inline void mod_add(int &a,int b){
    if((a+=b)>=mod)a-=mod;
}
int fast_mod_pow(int a,int b){
    int res=;
    for(;b;b>>=,(a*=a)%=mod)
        if(b&)(res*=a)%=mod;
    return res;
}
const int N=(int)+;
int n,cnt_zero,num[N];
void Gauss(){
    int ptr=;
    for(int mask=<<,i;mask;mask>>=){
        for(i=ptr;i<n;++i)
            if(num[i]&mask)
                break;
        if(i==n)continue;
        swap(num[ptr],num[i]);
        for(i=;i<n;++i)
            if(i!=ptr&&num[i]&mask)
                num[i]^=num[ptr];
        ++ptr;
    }
    cnt_zero=n-ptr;
    n=ptr;
}
int main(){
    rd(n);
    for(int i=;i<n;++i)
        rd(num[i]);
    int tar;
    rd(tar);
    if(!tar)return puts("1");
    Gauss();
    int ans=;
    for(int i=,cur=;i<n;++i){
        if((cur^num[i])<tar){
            cur^=num[i];
            mod_add(ans,fast_mod_pow(,n--i));
        }
    }
    mod_add(ans,);
    (ans*=fast_mod_pow(,cnt_zero))%=mod;
    mod_add(ans,);
    printf("%d\n",ans);
    return ;
}
/*

    Jul.19.16

    Tags:math,xor,Gauss Elimination
    Submissions:2

    Memory 1684kb
    Time 232ms
    Code Length 2034B

*/