Tang-Dreamoon's Blog

bzoj 2844 albus就是要第一个出场

发表于 | 分类于 ，

线性基模板题

　　题目链接：bzoj 2844

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：题目本意就是求不去重异或空间中 X 排在第几。求出异或空间的秩 M，则去重异或空间的大小为2^m，不去重异或空间的大小为2^n。任何一个包含线性基的子集都能够构成整个异或空间，故每一种非线性基的取法与线性基组合，都能够将整个异或空间遍历一次。故去重异或空间中的每个值在不去重异或空间中都出现2^(n-m)次。所以我们可以使用数位 DP 与线性基在去重异或空间内求出比 X 小的有几个，乘2^(n-m)+1就是答案了。

　　我思故我在：虽然这是一个水题——线性基的模板题，但我还是犯了一个十分脑残、智障、二逼、逗逼、水水的错误，咳咳~注意！N 很大 2^(n-m) 不能直接靠左移得出……

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
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n,k;
int modd=10086;
int stack[100100];
bool vis[100100];
int map[100100];
int er[100100];
int find()
{
	int maxa=0;
	int fr=0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			if(stack[i]>maxa)
			{
				maxa=stack[i],fr=i;
			}
		}
	}
	return fr;
}
void make()
{
	map[1]=0;
	for(int i=2;i<=65566;i++)
		map[i]=map[i/2]+1;
	er[0]=1;
	for(int i=1;i<=100000;i++)
		er[i]=(er[i-1]*2)%modd;
}
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	make();
	int tot=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&stack[i]);
	}
	scanf("%d",&k);
	int head;
	while(head=find())
	{
		tot++;
		int x=(stack[head]>>16),now;
		if(x==0) now=map[stack[head]];
		else now=map[x]+16;
		for(int i=1;i<=n;i++)
		{
			if(((1<<now)&stack[i])!=0&&i!=head)
			{
				stack[i]=stack[i]^stack[head];
			}
		}
		vis[head]=1;
	}
	sort(stack+1,stack+1+n,cmp);
	int now=0;
	long long ans=0;
	for(int i=1;i<=tot;i++)
	{
		if((now^stack[i])<=k)
		{
			now=now^stack[i];
			ans=(ans+er[tot-i]%modd)%modd;
		}
	}
	ans=(ans*er[n-tot]%modd+1)%modd;
	cout<<ans<<endl;
	return 0;
}