http://acm.hdu.edu.cn/showproblem.php?pid=3949

求異或第k小，結論是第k小就是 k二進制的第i位為1就把i位的線性基異或上去。

但是這道題和上一道線性基不同的地方是要縮一下位使得k的每一位都有線性基(畢竟是組合為基礎的)。

要在往里塞線性基的時候把每個線性基上的1能往后放的盡量往后放emmm這么搞非常重要，以后寫線性基都加一下這個可以處理的東西更多了。

(這個東西維護之后，線性基中所有數都變為二進制的話那么每個二進制位上至多有一個1)

這道題不能取空集所以還要注意一下0能不能取到。

沒了。

感謝一下這位神犇的代碼?https://www.cnblogs.com/kkkkahlua/p/7800932.html

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define LL long long 8 int n,m,f=0; 9 LL b[65]={},c[65]={}; 10 inline void init(LL x){ 11 for(int i=60;i>0;i--){ 12 if(x&c[i]){ 13 if(!b[i]){ 14 for(int j=1;j<i;++j)if((x>>(j-1))&1)x^=b[j]; 15 for(int j=i+1;j<=60;++j)if((b[j]>>(i-1))&1)b[j]^=x; 16 b[i]=x;break; 17 } 18 x^=b[i]; 19 if(!x)f=1; 20 } 21 } 22 } 23 inline LL getit(LL x){ 24 LL ans=0; 25 for(int i=60;i>0;i--){ 26 if(x&c[i]){ 27 ans^=b[i]; 28 } 29 } 30 return ans; 31 } 32 int main(){ 33 int T,cc=0;LL x; 34 scanf("%d",&T); 35 while(T-->0){ 36 scanf("%d",&n); 37 c[1]=1;b[1]=0;f=0; 38 for(int i=2;i<=60;i++){b[i]=0;c[i]=c[i-1]*2;} 39 for(int i=1;i<=n;i++){scanf("%lld",&x);init(x);} 40 int siz=1; 41 for(int i=1;i<=60;i++){if(b[i]){b[siz]=b[i];++siz;}}--siz; 42 printf("Case #%d:\n",++cc); 43 scanf("%d",&m); 44 LL sz=((long long)1<<(siz))-1; 45 for(int j=0;j<m;j++){ 46 scanf("%lld",&x); 47 if(f)--x; 48 if(x>sz)printf("-1\n"); 49 else printf("%lld\n",getit(x)); 50 } 51 } 52 return 0; 53 } View Code

?

?

?

轉載于:https://www.cnblogs.com/137shoebills/p/8832406.html

總結

以上是生活随笔為你收集整理的HDU 3949 XOR 线性基的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。