题目大意:给定 k 位二进制下的 n 个数,求 [l,r] 区间内有多少个数能通过这几个数与非得到
首先观察真值表 我们有 A nand A = not A
然后就有 not (A nand B) = A and B
与和非都弄到了,我们就能够做出一切逻辑运算了,比方说或和异或
A or B = not ((not A) and (not B) )
A xor B = (A or B) and (A nand B)
然后我们对于位运算能够发现一个性质
对于某两位来说。假设对于每个数。这两位上的值都是同样的,那么这两位不管怎么计算终于结果都会是同样的
比方说 10(1010) 和 7(0111),第一位和第三位都是同样的。所以最后不管怎么计算,这两位都是一样的
然后我们这么处理:
对于每一位,我们枚举每个数,若该数该位上为 0。我们就对这个数取非
然后把全部数取与
该位上都是 1,所以取与后一定是 1。对于其它位,仅仅要有这两位不同的数存在,那么这位一定是 0
最后取与的结果中与该位所有同样的位都是 1,其余都是 0
对于每一位这样处理,标记去重,然后能够得到线性基,保证每一位存在且仅存在于线性基中的一个数上
拿去从大到小贪心处理就可以 得到二进制序列即为答案
此题有坑 题目描写叙述中 1<=L<=R<=10^18 可是第七个点 L=0 坑死一票人啊
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define M 1010
- using namespace std;
- typedef long long ll;
- int n,k;
- ll digit,l,r,a[M],basis[70],tot;
- bool v[70];
- ll Get_Digit(ll x)
- {
- if(x==-1)
- return -1;//坑比!!!
- ll now=0,re=0;
- int i;
- for(i=1;i<=tot;i++)
- if( (now|basis[i])<=x )
- now|=basis[i],re|=(1ll<<tot-i);
- return re;
- }
- int main()
- {
- //freopen("nand.in","r",stdin);
- //reopen("nand.out","w",stdout);
- int i,j;
- ll now;
- cin>>n>>k>>l>>r;
- digit=(1ll<<k)-1;
- for(i=1;i<=n;i++)
- scanf("%lld",&a[i]);
- for(i=k-1;~i;i--)
- if(!v[i])
- {
- now=digit;
- for(j=1;j<=n;j++)
- if( a[j]&(1ll<<i) )
- now&=a[j];
- else
- now&=~a[j]&digit;
- basis[++tot]=now;
- for(j=0;j<=i;j++)
- if( now&(1ll<<j) )
- v[j]=1;
- }
- cout<<Get_Digit(r)-Get_Digit(l-1)<<endl;
- }
- //lld
来源: http://www.bubuko.com/infodetail-2145834.html