BZOJ 2728: [HNOI2012]与非

2728: [HNOI2012]与非

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 786 Solved: 371
[Submit][Status][Discuss]

Description

Input

输入文件第一行是用空格隔开的四个正整数N，K，L和R，接下来的一行是N个非负整数A1,A2……AN，其含义如上所述。 100%的数据满足K≤60且N≤1000,0<=Ai<=2^k-1,0<=L<=R<=10^18

Output

仅包含一个整数，表示[L,R]内可以被计算出的数的个数

Sample Input

3 3 1 4
3 4 5

Sample Output

HINT

样例1中，(3 NAND 4) NADN (3 NAND 5) = 1，5 NAND 5 = 2，3和4直接可得。

Source

day1

分析：

如果把与非操作换成异或操作应该就是裸的线性基的题目，现在问题就转化为了求与非操作下的线性基...

我们考虑通过与非操作可以得到所有的位运算：

$~A=A nand A$

$A and B=~(A nand B)$

$A orB=~((~A) and (~B))$

$A xor B=(A or B) and (A nand B)$...

然后我们发现所有的位运算，对于某些位置，如果这些位置在每个数字中都相同，那么最后的结果这些位置也是相同的...

而因为我们可以得到所有的位运算所以这些位置最后都可以为$1$，所以我们找出所有相同的位置作为线性基，一组相同的位置是线性基中的一个数...计算出线性基之后随便算一算就好了...

具体找法就是我们选取当前枚举的位置，如果一个数字当前位置为$0$那么把它取反，然后把操作之后的所有数字$and$起来，这样相同的位置一定是$1$...

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define int long long
using namespace std;

const int maxn=1000+5;

int n,k,l,r,cnt,a[maxn],b[maxn],f[maxn];

inline int calc(int x){
	if(x==-1)
		return -1;
	int now=0,ans=0;
	for(int i=1;i<=cnt;i++)
		if((now|b[i])<=x)
			now|=b[i],ans|=(1LL<<cnt-i);
	return ans;
}

inline void xor_gauss(void){
	int lala=(1LL<<k)-1,now;
	for(int i=k-1;i>=0;i--)
		if(!f[i]){
			now=lala;
			for(int j=1;j<=n;j++){
				if((a[j]>>i)&1)
					now&=a[j];
				else
					now&=~a[j]&lala;
			}
			b[++cnt]=now;
			for(int j=0;j<=i;j++)
				if((now>>j)&1)
					f[j]=1;
		}
}

signed main(void){
	scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	xor_gauss();
	printf("%lld
",calc(r)-calc(l-1));
	return 0;
}

By NeighThorn