【題目描述】
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) //如果這個數字在這一位有數字，那么排名就向前移動1<<i位（在0的基礎上）{ans+=1<<i; //這里的i是指這一位前面有多少個高位，也就是說如果這一位是0的數字個數，加上它就是在0的基礎上向前移動的排名}}//printf("test: ans=%d num=%d p[0]=%d\n",ans,num,p[0]);return ans+1;//因為前面還有一個0，所以要+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); //用快速冪算2^n-num
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;}}//printf("test: ans=%d num=%d p[0]=%d\n",ans,num,p[0]);return (ans*quick_pow(2,n-num))%MOD+1;//ans本來是要+1再-1的，這里就省略了（我之前看其他博客他們好像都沒有講這個然后我就好久都不能理解，emmm,還是太菜了）}
};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);//printf("%lld",quick_pow(2,5));return 0;
}
