HNOI2012与非

HNOI2012与非

发现用与非可以实现一切操作

[not A=AnandA ]

[AorB=not((notA)nand(notB)) ]

[AandB=not(AnandB) ]

[AxorB=not(((notA)and(notB))or(AandB)) ]

发现若n个数的某两位相等，那么无论怎么操作，最后都相等，其余没限制的可以随意填0/1

证明可以用线性基思想，我们总能构造出只有这些相等位为1，剩下的为0的数来，然后随意选几个数异或成为最后的答案（把这一为为0的数取反，然后把所有数异或到一起）

然后数位DP即可

//starusc
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
int pos[64],b[64];
int dp(int n,int p,int fl){
	if(p==-1)return 1;
	int ret=0;
	if(!fl){
		for(int i=0;i<=p;i++)
			if(!pos[i])ret++;
		return 1ll<<ret;
	}
	int mx=(n>>p)&1;
	if(pos[p]){
		if(b[pos[p]]<=mx)return dp(n,p-1,b[pos[p]]==mx);
		return 0;
	}
	for(int i=0;i<=mx;i++){
		b[p]=i;
		ret+=dp(n,p-1,i==mx);
	}
	return ret;
}
int k;
inline int solve(int n){
	if(n==-1)return 0;
	return dp(n,k-1,(n>>k)?0:1);//
} 
int n,L,R,a[1004];
signed main(){
	n=read();k=read();L=read();R=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int u=0,fl;u<k;u++)
		for(int v=k-1;v>u;v--){
			fl=1;
			for(int i=1;i<=n;i++)
				if(((a[i]>>u)&1)^((a[i]>>v)&1)){fl=0;break;}//
			if(fl){pos[u]=v;break;}
		}
	cout<<solve(R)-solve(L-1);
	return (0-0);
}