【題目描述】
BZOJ 2844 | HYSBZ - 2844albus
【題目分析】
題目的意思大概是給一個數列，他有2n個子集，每個子集的元素的異或和構成新的一個數列，排序后問數字Q在這個序列里面的下標。
假如題目是求所有元素的異或和構成一個集合就好弄了，我們可以根據求第K大反過來求他在集合里面的下標。
int find_ans(int q
){int num
=0; int ans
=0;vector
<int> p
;for(int i
=0;i
<=62;i
++){if(b
[i
]){p
.push_back(i
); num
++;}}for(int i
=num
-1;i
>=0;i
--){if(q
>>p
[i
]&1) {ans
+=1<<i
; }}return ans
+1;}
可是我們知道這樣肯定是求不出答案的，還有好多重復的數字，我們不妨來分析一下這些重復 的數字。對于線性基異或出來的一個數字x，所有和他重復的數字肯定是由那些不包含在線性基里面的數字幫忙異或出來的。
原因是線性基的兩個性質：
1.線性基異或出來的數字不相同。
2.線性基無法異或出0。
而這里其他重復的數字相當于線性基的一部分數字異或出 x后再異或一些0（異或0不會改變數值），而通過上面的分析我們知道這些0只能是那些沒有進入線性基的數字和一部分進入線性基的 數字異或出來的（當然也可能不包含線性基里面的數字，但肯定不是純線性基的數字），那么我們能異或出多少個0呢？對于線性基外的每一個數字我們都可以用線性基里面的一部分數字異或出來，所以線性基外的每一個數字配合線性基里的一部分數字都能異或出0，可是不同的0有多少個？我們不妨將線性基外的數字放入一個集合，這個集合的所有子集配合他們相應的能夠異或出他們的線性基的數字就能異或出不同的0。而這個子集的個數很好求，2n-num個，n-num為線性基外的數字個數。
所以，我們要做的就是算出q-1前面有多少個數字，然后乘2n-num，再+1就是第一個q的位置。
我們不妨借用上面的程序，上面算出的是在不重復的集合中q的下標，那前面就是（下標-1）*2n-num+1就是答案了。
【AC代碼】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>using namespace std
;typedef long long ll
;const int MAXN
=100005;
const int MOD
=10086;
int n
,q
,tmp
;
ll
quick_pow(ll a
,ll b
);
struct L_B
{ll b
[65],p
[65];int cnt
,flag
;L_B(){memset(p
,0,sizeof(p
));memset(b
,0,sizeof(b
));cnt
=flag
=0;}void clear(){memset(p
,0,sizeof(p
));memset(b
,0,sizeof(b
));cnt
=flag
=0;}inline bool insert(ll x
){for(int i
=62;i
>=0;--i
)if(x
&(1ll<<i
)){if(b
[i
])x
^=b
[i
];else{b
[i
]=x
;return true;}}flag
=1;return false;}ll
get_max(){ll ret
= 0;for(int i
=62;i
>=0;--i
)if((ret
^b
[i
])>ret
)ret
^=b
[i
];return ret
;}ll
get_max(ll initval
){ll ret
= initval
;for(int i
=62;i
>=0;--i
)if((ret
^b
[i
])>ret
)ret
^=b
[i
];return ret
;}ll
get_min(){if(flag
)return 0;for(int i
=0;i
<=62;++i
)if(b
[i
])return b
[i
];return 0;}inline void rebuild(){for(int i
=1;i
<=62;++i
)if(b
[i
])for(int j
=0;j
<i
;++j
)if(b
[i
]&(1ll<<j
))b
[i
]^=b
[j
];for(int i
=0;i
<=62;++i
)if(b
[i
])p
[cnt
++]=b
[i
];}ll
kth(ll k
){if(flag
)--k
;if(k
==0)return 0;ll ret
= 0;if(k
>=(1ll<<cnt
))return -1;for(int i
=0;i
<=cnt
-1;++i
)if(k
&(1ll<<i
))ret
^=p
[i
];return ret
;}int find_ans(int q
){int num
=0; int ans
=0;vector
<int> p
;for(int i
=0;i
<=62;i
++){if(b
[i
]){p
.push_back(i
);num
++;}}for(int i
=num
-1;i
>=0;i
--){if(q
>>p
[i
]&1){ans
+=1<<i
;}}return (ans
*quick_pow(2,n
-num
))%MOD
+1;}
};ll
quick_pow(ll a
,ll b
)
{ll ret
=1;while(b
){if(b
%2) ret
=(ret
*a
)%MOD
;a
=a
*a
%MOD
;b
>>=1;}return ret
;
}int main()
{L_B lis
;int ans
=0;scanf("%d",&n
);for(int i
=0;i
<n
;i
++){scanf("%d",&tmp
);lis
.insert(tmp
);}scanf("%d",&q
);printf("%d",lis
.find_ans(q
)%MOD
);return 0;
}
總結
以上是生活随笔為你收集整理的BZOJ 2844 | HYSBZ - 2844albus就是要第一个出场——线性基的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
