「bzoj2844」albus就是要第一个出场 - 线性基 | Bill Yang's Blog

「bzoj2844」albus就是要第一个出场 - 线性基

题目大意

    给定$n(n\le10000)$个数$a_i$,以及一个数$Q$。将$a$的所有子集(可以为空)的异或值从小到大排序得到序列$B$,请问$Q$在$B$中第一次出现的下标是多少?保证$Q$在$B$中出现。


题目分析

首先求出$a$的线性基$\frak B$,然后考虑如何求出$Q$的排名。
若题目不计重复,那么就和本题类似,用二进制的方法即可确定$Q$的排名。
结论:所有数都出现一样的次数,均为$2^{n-\left|\frak B\right|}$次。
证明:
所有不在线性基中数的个数为$n-\left|\frak B\right|$个,我们任意选择一个子集$S$,因为其线性相关,因此可以唯一表示为$\frak B$中向量的线性组合。
因此,我们至少有$2^{n-\left|\frak B\right|}$种方法使异或值为$0$,因此每个数至少出现$2^{n-\left|\frak B\right|}$次。
又因为每个数在$\frak B$中表示方法是唯一的,故只有不在线性基中才可能组成多种方案,故上界也是$2^{n-\left|\frak B\right|}$,命题得证。

这样我们就只需要求出二进制表示后进行快速幂即可。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int MAX_BASE=30,mod=10086;
struct Linear_Bases {
int b[MAX_BASE+5];
vector<int>a;
void build(vector<int> a) {
for(int num:a)
for(int j=MAX_BASE; j>=0; j--)
if(num>>j&1) {
if(b[j]) { //该位存在基
num^=b[j];
continue;
}
b[j]=num;
for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
break;
}
}
void split() {
for(int i=0; i<=MAX_BASE; i++)if(b[i])a.push_back(i);
}
} lb;
int Quick_Pow(int a,int b) {
int ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int n,Q;
vector<int>a;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a.push_back(Get_Int());
lb.build(a);
lb.split();
Q=Get_Int();
int rank=0;
for(int i=0; i<lb.a.size(); i++)if(Q>>lb.a[i]&1)rank^=1<<i;
printf("%d\n",(rank%mod*Quick_Pow(2,n-lb.a.size())%mod+1)%mod);
return 0;
}
0%