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\n",calc(r)-calc(l-1));

	return 0;

}

By NeighThorn

巴特西