记录编号	417694	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012]与非	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-06-26 23:57:50	内存使用	0.32 MiB

#include<cstdio>
typedef long long ll;
const int N=1010;
int n,k,fa[N];
ll l,r,a[N],sum[N],cnt[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
ll calc(ll n){//求[1,n]中的答案 
	if (n<0) return -1;
	ll ans=0;
	for (int i=k-1;i>=0;i--)
	if (fa[i]==i&&n>=sum[i])//可以选择取不取 
		n-=sum[i],ans+=(1ll<<(i?cnt[i-1]:0));
	return ans;
}
int main()
{
	freopen("bzoj_2728.in","r",stdin);
	freopen("bzoj_2728.out","w",stdout);
	scanf("%d%d%lld%lld",&n,&k,&l,&r);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (int i=0;i<k;i++) fa[i]=i;
	for (int i=0;i<k;i++)
	for (int j=0;j<i;j++){
		for (int x=1;x<=n;x++)
			if ((a[x]>>i&1)^(a[x]>>j&1)) goto nxt;
		fa[find(j)]=find(i);
		nxt:;
	}
	for (int i=0;i<k;i++) sum[find(i)]|=(1ll<<i);
	for (int i=0;i<k;i++) if (i==fa[i]) cnt[i]++;
	for (int i=1;i<k;i++) cnt[i]+=cnt[i-1];
	printf("%lld\n",calc(r)-calc(l-1));
	return 0;
}