【BZOJ 2844】: albus就是要第一个出场

时间：2023-03-09 14:31:39
【BZOJ 2844】: albus就是要第一个出场

题目大意：

　　给一个长度为n的序列，将其子集的异或值排序得到B数组，给定一个数字Q，保证Q在B中出现过，询问Q在B中第一次出现的下标。

题解：

　　感觉和hdu3949第K小异或值有一像，然而发现要求出现次数……emmmm

　　考虑线性基的性质，即在n个数字中求出其极大线性无关子集，设其长度为m，也就意味着有n-m个元素是可以用这m个元素表示的，考虑假设我们现在用这m个变量表示出了一个数字A，那么给A异或上0还是其本身，考虑剩下的n-m个元素可以凑多少个0,即二项式定理，所以可以知道，对于任意一个可以用线性基表示出来的数，其出现次数均为$2^{n-m}$。

代码：

 #include "bits/stdc++.h"

 using namespace std;

 inline int read(){

     int s=,k=;char ch=getchar();

     while(ch<''|ch>'') ch=='-'?k=-:,ch=getchar();

     while(ch>&ch<='') s=s*+(ch^),ch=getchar();

     return s*k;

 }

 const int N=1e5+,mod=;

 int a[N],bin[],b[],n,Q,m,cnt,ans;

 inline int powmod(int a,int b){

     int ret=;

     while(b){

         if(b&) ret=ret*a%mod;

         b>>=,a=a*a%mod;

     }return ret;

 }

 int main(){

     n=read();

     register int i,j,k;

     for(i=;i<=n;++i) a[i]=read();

     for(i=;i<=;++i)bin[i]=<<i;

     for(i=;i<=n;++i)

         for(j=;~j;--j) if(a[i]&bin[j])

             if(b[j]) a[i]^=b[j];

             else  {

                 b[j]=a[i];++cnt;

                 for(k=j-;~k;--k) if(b[k]&&(b[j]&bin[k])) b[j]^=b[k];

                 for(k=j+;k<=;++k) if(b[k]&bin[j]) b[k]^=b[j];

                 break;

             }

     for(i=;i<=;++i)  if(b[i])    a[m++]=i;

     Q=read();

     for(i=;i^m;++i)   if(Q&bin[a[i]])

         ans|=bin[i];

     ans%=mod;

     printf("%d\n",(ans*powmod(,n-cnt)%mod+)%mod);

 }

相关文章