Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

题面传送门

这题需要解决两个问题,一个是x在线性基里排第几,一个是每个数出现了几次。

对于问题①,我们已经知道了如何求出去重后B数组的第k小,而这题其实是反过来的给你一个数q,求出它是第几小。

步骤:
1. 求出线性基后线性基内所有元素从小到大排序,并且只保留最高位
2. 之后将q二进制拆分,初始化rank=0,如果q的第i位为1,就看线性基中是否存在一个数x满足x = (1<<i),如果存在,那么rank = rank^(x在线性基中排名),最后的rank就是q的排名-1,为什么是排名-1呢因为还有个0没有算。

对于问题②,定理:B数列中每个数字出现次数都是2^{(n-cnt)},其中cnt是线性基的大小(我也不会证

#include <cstdio>
using namespace std;

typedef long long LL;
const int Maxn=1e5+5,Mod=10086;

int N,A[Maxn],K,B[Maxn],Cnt,Ans;
int Ksm(int x,int y){
    int res=1;for(;y;y>>=1,x=(LL)x*x%Mod)if(y&1)res=(LL)res*x%Mod;return res;
}

void Ins(int x){
    for(int i=30;~i;i--){
        if((x>>i)&1){
            if(!B[i]){B[i]=x;break;}
            x^=B[i];
        }
    }
}

int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)scanf("%d",&A[i]),Ins(A[i]);
    scanf("%d",&K);
    for(int i=0;i<=30;i++)if(B[i]){
        if((K>>i)&1)Ans+=1<<Cnt;++Cnt;
    }printf("%lld",(1ll*Ans*Ksm(2,N-Cnt)+1)%Mod)
;}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*