【HNOI2012】与非

先%徐子犇大神犇

这题显然是个数学题

显而易见的是与非是与和非操作的结合:a NAND b=~(a&b)

那么可以得到最重要的结论:四种位运算都可以用NAND表示出来

因为a&a=a,得到~a=a NAND a

那么a&b=~(a NAND b)

a|b=~((~a)&(~b))

a^b=(a|b)&(a NAND b)

所以用与非可以完成所有位运算

但还是有一些不能被所给数表示出来的数:若每个所给数第i位和第j位都相同,那么第i位和第j位不同的数是不能被表示出来的。

一开始两两判断一下,标记位数小的向位数大的连一条边,说明这些位数小的受位数大的限制,同时统计受限制的数个数。

然后对于[L,R],统计[0,R]-[0,L-1]的答案即可

从高位往低位走,若某一位不受限制则已决策数++,

  1. 若该位为0且不受限制,continue;
  2. 若该位为0且受限制,若限制它的位为1则break,否则continue;
  3. 若该位为1且不受限制,ans+=1<<(k-受限制数-已决策数)(该位取0时后面未受限制的可以随意取);
  4. 若该位为1且受限制,若限制它的位为0,ans+=1<<(k-受限制数-已决策数)并break,否则continue。

正确性显而易见

但是这样的话只能统计[0,x),当x满足条件时无法被统计到

所以答案为get(R+1)-get(L)

说点什么

您将是第一位评论人!

提醒
wpDiscuz