题目大意
给定$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;
}
|
