albus就是要第一个出场(线性基)

这个题题目描述真怪异……就不能说人话吗……

人话：给定长为n的序列A，定义f(s)为集合s内所有元素异或值，求A的所有子集的f值从小到大排列后，q在其中第一次出现的下标对10086取模的值。

首先不难想到构建线性基。线性基有一个良好的性质！假设这n个数的线性基中有k的数，那么显然有\(2^k\)种异或值。之后，因为线性基是可以看作线性基中本来有的数再加上一堆0，所以每一种异或值应该出现过\(2^{n-k}\)次。

那么我们只需要求出来q在这一堆异或值中的排名。这个我们可以仿照求第k大的操作（鬼知道为啥我hdu过不了），看一下代码吧。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#include<cstring>

#define rep(i,a,n) for(register int i = a;i <= n;i++)

#define per(i,n,a) for(register int i = n;i >= a;i--)

#define enter putchar('\n')

#define pr pair<int,int>

#define mp make_pair

#define fi first

#define sc second

#define I inline

using namespace std;

typedef long long ll;

const int M = 100005;

const int N = 10000005;

const int mod = 10086;

const double eps = 1e-5;

int read()

{

   int ans = 0,op = 1;char ch = getchar();

   while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}

   while(ch >='0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();

   return ans * op;

}

int n,a[M],p[60],q,b[60],cnt,tot;

int inc(int a,int b) {return (a+b) % mod;}

int mul(int a,int b) {return 1ll * (a) * (b) % mod;}

int qpow(int a,int b)

{

   int c = 1;

   while(b)

   {

      if(b & 1) c = mul(c,a);

      a = mul(a,a),b >>= 1;

   }

   return c;

}

void insert(int x)

{

   per(i,30,0)

   {

      if(!((x >> i) & 1)) continue;

      if(!p[i]) {p[i] = x;break;}

      x ^= p[i];

   }

}

int main()

{

   n = read();

   rep(i,1,n) a[i] = read(),insert(a[i]);

   rep(i,0,30) if(p[i]) b[cnt++] = i;

   q = read();

   rep(i,0,cnt-1) if((q >> b[i]) & 1) tot += 1 << i;

   printf("%d\n",inc(mul(tot,qpow(2,n-cnt)),1));

   return 0;

}

巴特西

albus就是要第一个出场(线性基)

最新文章

热门文章