首页 > 代码库 > bzoj2844 albus就是要第一个出场

bzoj2844 albus就是要第一个出场

题意:http://www.lydsy.com/JudgeOnline/problem.php?id=2844

sol  :因为这个是不去重空间,所以麻烦点QAQ

   考虑去重空间的做法,直接线性基+树形dp即可

   而对于不去重空间,其大小为2^n,求出异或空间的秩m,则去重空间的大小为2^m

   那么去重异或空间的每个值在不去重异或空间里出现2^(n-m)次

   所以答案即为去重异或空间的答案*2(n-m)+1即可

   记得开long long

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int Mx=100010;
const int p=10086;
int n,m,x,q,rank,now,a[Mx];
void gauss()
{  
    now=1,m=31;
    while(m--)
        for(int i=now;i<=n;i++)
            if(a[i]&(1<<m))
            {
                swap(a[i],a[now]);
                for(int j=1;j<=n;j++)
                    if(j!=now&&(a[j]&(1<<m))) a[j]^=a[now];
                now++; break;
            }
    now--;
}
signed main()  
{  
    scanf("%lld",&n);  
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);  
    scanf("%lld",&q);  
    gauss();
    for(int i=1;i<=now;i++)
    {  
        if((x^a[i])>q) continue;
        x^=a[i];
        rank=(rank+(1<<(now-i)))%p;
    }  
    for(int i=1;i<=n-now;i++) rank=(rank<<1)%p;
    printf("%lld\n",(rank+1)%p);
    return 0;
}

 

bzoj2844 albus就是要第一个出场