a不能由b，LOJ.114.K大異或和(線性基)

題目鏈接

如何求線性基中第K小的異或和？好像不太好做。
如果我們在線性基內部Xor一下，使得從高到低位枚舉時，選base[i]一定比不選base[i]大(存在base[i])。
這可以重構一下線性基，從高到低位枚舉i，如果base[i]在第j位(j<i)有值，那么Xor一下base[j]。（保證每一列只有一個1）
比如 1001(3)與0001(0)，同時選0,3只比3要小；重構后是 1000(3)和0001(0)，這樣同時選0,3比只選0或3都要大。
這樣將K二進制分解后就可以直接對應上線性基對應位的選擇了。要存base[i]有值的i。

需要注意如果線性基中表示的向量不足n個，說明一定存在一組向量滿足線性相關關系，即存在Xor和為0的情況。這樣要使K減1。
判斷是K>=(1<<size)，線性基和的個數是2^{size}-1(不算0)。

#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 100000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define Bit 51
typedef long long LL;
const int N=1e5+5;int n,size,cnt;
LL base[69],b2[69];
char IN[MAXIN],*SS=IN,*TT=IN;inline LL read()
{LL now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}
inline void Insert(LL x)
{for(int i=Bit; ~i; --i)if(x>>i & 1)if(base[i]) x^=base[i];else {base[i]=x, ++size; break;}
}
inline LL Query(LL K)
{LL ans=0;for(int i=cnt; ~i; --i)if(K>>i & 1) ans^=b2[i];return ans;
}
void Rebuild()
{for(int i=Bit; ~i; --i)for(int j=i-1; ~j; --j)if(base[i]>>j & 1) base[i]^=base[j];for(int i=0; i<=Bit; ++i) if(base[i]) b2[cnt++]=base[i];
}int main()
{n=read();for(int i=1; i<=n; ++i) Insert(read());Rebuild();for(int Q=read(); Q--; ){LL K=read()-(size!=n);//別在for里開int啊mmp printf("%lld\n",(K>=(1ll<<size))?-1ll:Query(K));}return 0;
}

有一種不需要重構線性基的方法：詢問時將K二進制拆分(按size位)，若K在第j位有1,且當前答案在第i位沒有1（還可以更大）或是 K在第j位沒有1,且當前答案在第i位有1(偏小？)，則ans^=base[i]。
不太理解。（隨大流吧。。）

#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 100000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define Bit 51
typedef long long LL;
const int N=1e5+5;int n,size;
LL base[69];
char IN[MAXIN],*SS=IN,*TT=IN;inline LL read()
{LL now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}
inline void Insert(LL x)
{for(int i=Bit; ~i; --i)if(x>>i & 1)if(base[i]) x^=base[i];else {base[i]=x, ++size; break;}
}
inline LL Query(LL K)
{LL ans=0;for(int i=Bit,now=size; ~i; --i)if(base[i])if((K>>(--now) & 1)^(ans>>i & 1)) ans^=base[i];return ans;
}int main()
{n=read();for(int i=1; i<=n; ++i) Insert(read());for(int Q=read(); Q--; ){LL K=read()-(size!=n);printf("%lld\n",(K>=(1ll<<size))?-1ll:Query(K));}return 0;
}