生活随笔
收集整理的這篇文章主要介紹了
【bzoj2844 albus就是要第一个出场】
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題意：給定一個n個數的集合S和一個數x,求x在S的2n2n個子集從小到大的異或和序列中最早出現的位置
根據性質每一個數字出現的次數是相同的都是2^(n-cnt)個，cnt是線性基中元素得個數
?
#include<bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <stdlib.h>
#include <ctime>
using namespace std;
typedef long long ll;
const int mod = 10086;
const int maxn = 1e6 + 5;
using namespace std;
int a[maxn];
int Pow(int a,int n){int ans=1;while(n){if(n&1)(ans*=a)%=mod;(a*=a)%=mod;n>>=1;}return ans;
}
int main(){int n,A;int cnt=0;cin>>n;for(int i=0;i<n;++i){cin>>A;for(int x=62;x>=0;--x){if(A&(1ll<<x)){//if((A[i]>>x)&1)if(a[x]==0){a[x]=A;cnt++;break;}A^=a[x];}}}int Q;cin>>Q;vector<int>vec;int ans=0;for(int i=0;i<=62;++i)if(a[i])//構造出來的最高位為1的就在第i位置vec.push_back(i);//存放位置for(int i=0;i<(int)vec.size();++i)if(Q>>vec[i]&1)ans+=1<<i;//前面多少個數比他小的數字個數，說明Q是第幾小的數(ans) //可以變形得到ansans=(ans%mod*Pow(2,n-cnt)%mod+1)%mod;cout<<ans<<endl;return 0;
}
?
總結
以上是生活随笔為你收集整理的【bzoj2844 albus就是要第一个出场】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
