自动搬运

查看原文

来自洛谷，原作者为

	Salamander **

搬运于2025-08-24 21:46:38，当前版本为作者最后更新于2018-02-02 10:54:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

与非($nand$)是非常强大的位运算，可以表示出其他所有的位运算：

$not\ A=A\ nand\ A$

$A\ and\ B=not\ (A\ nand\ B)$

$A\ or\ B=(not\ A)\ nand\ (not\ B)$

$A\ xor\ B=(A\ and\ not\ B)\ or\ (not\ A\ and\ B)$

所以相当于是这$n$个数之间可以做任何位运算。

然后我们考虑一下位与位之间的限制。如果这$n$个数中每个数的第$i$位和第$j$位都相同，那么这$n$个数无论怎么运算，最后得到的答案中第$i$位和第$j$位一定相同。我们在数位dp的时候从高位到低位考虑，确定了当前位后把必须和它相同的位也标记一下，就可以求出$[1,n]$中能运算出的数的个数。

$~$

为什么这样是对的?其他没有互相限制的位置上就一定可以任意取$0$或$1$了吗?

$~$

类似于线性基的思想，我们可以构造这样一种方案：通过一些运算把某一位上只留下一个$1$，其他的数在这一位上都为$0$，最后用它们或起来就可以构造出任意一个数。对于第$i$位，假设没有限制，那么我们把这一位上为$0$的数全都取反，然后全部与起来，得到的数这一位上肯定是$1$；同时由于这一位没有限制，所以不会有其他位置上再出现一个$1$，因为如果还出现$1$就表每一个数中那一位与第$i$位都相等，于是就产生了限制，矛盾。所以对于没有限制的位，我们一定可以构造出一个只有这一位上为$1$的数。对于几个必须相等的位，这样可以构造出一个只有这几位为$1$的数。

于是我们可以把$n$个数构造出一个类似这样的东西，假设最左边第$1$位，那么下面这个东西中间的限制就是第$3$位和第$5$位必须相等，第$8$位和第$9$位必须相等。

10000000
01000000
00101000
00010000
00000100
00000011

利用这样的东西，我们通过他们之间的或运算，就可以构造出原来$n$个数所能构造出的所有数，所以数位dp就可以直接做了。首先暴力求出哪些位必须相等。

复杂度应该是$O(nk^2)$。

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)

template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
	T f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	x*=f;
}

typedef long long LL;
const int maxn=1010;
int n,k,c[65],tmp[65];
LL a[maxn],L,R;
vector<int>pos[65];

LL Dfs(LL n,int x,bool lim){
	if(x<0)return 1;
	if(!lim){
		int cnt=0;
		memcpy(tmp,c,sizeof c);
		Rep(i,x,0) if(tmp[i]==-1){
			cnt++;
			For(j,0,pos[i].size()-1) tmp[pos[i][j]]=1;
		}
		return 1LL<<cnt;
	}
	LL res=0;
	if(c[x]==-1){
		For(i,0,(n>>x)&1){
			For(j,0,pos[x].size()-1) c[pos[x][j]]=i;
			res+=Dfs(n,x-1,lim&(i==((n>>x)&1)));
		}
		For(j,0,pos[x].size()-1) c[pos[x][j]]=-1;
		return res;
	}
	else{
		if(c[x]&&lim&&!((n>>x)&1))return 0;
		return Dfs(n,x-1,lim&(c[x]==((n>>x)&1)));
	}
}
LL Solve(LL x){
	memset(c,-1,sizeof c);
	if(x<0)return 0;
	return Dfs(x,k-1,(x>>k)?0:1);
}

int main(){
	read(n);read(k);read(L);read(R);
	For(i,1,n) read(a[i]);
	Rep(i,k-1,1) Rep(j,i-1,0){
		bool flag=true;
		For(p,1,n) if(((a[p]>>i)&1)^((a[p]>>j)&1)){
			flag=false;
			break;
		}
		if(flag) pos[i].push_back(j);
	}
	printf("%lld\n",Solve(R)-Solve(L-1));
	return 0;
}