求n个k位二进制数的与非 (a NAND b = NOT (a AND b)) 空间跟[l,r]的交集大小. (n≤1000, 0≤l≤r≤10^18, 所有数以十进制给出, 保证合法) 首先, 与非空间即位运算 (AND, OR, NOT) 空间. 前者是后者的子集, 而
NOT a = a NAND a
a AND b = NOT (a NAND b)
a OR b = NOT ((NOT a) AND (NOT b))这道题听人讲过, 但是没学会......NAND能实现所有位运算, 但是位运算空间我也不熟悉啊......
去Po姐的博客学习一发, 原来是这样的:
一个数能由某集合中的数相互位运算生成 <=> 如果集合中所有数的i, j位值都相等, 则该数的i, j位相等
举例: 集合{10110, 01011, 11011}. 数11010不能由这个集合生成.
=>: 若a=b且c=d, 则a x c = b x d, x为任意位运算.
<=: 构造. 枚举i=k-1,k-2,...,0, 对每个数, 若第i位为0, 则取反, 否则不变, 这样, 某位为1当且仅当它和第i位相等. 把它们与起来, 则得到在每个数中都与该数第i位相等的位, 同时, 得到的这个数是由位运算生成的. 把得到的所有数去重, 构成集合S. 如果待生成的数x的第i位为1, 取S中第i位为1的元素y (存在且唯一), 则y中所有等于1的位在x中也等于1. 枚举i, 把对应的y与起来, 则得到x.
这个构造的方法也是本题的解法. 求出集合S, 做数位统计即可. 怎样得到[1,x]的答案呢? 贪心地构造出不大于x且能生成的最大数, 统计位运算空间中小于它的数的个数, 加上1. 注意l, r可以等于0.
没搞出来的原因大概是: 1. 方向错误, 以为得转化为异或运算来搞事情. 2. 没有大胆猜想; 有些必要条件实际上是充分的, 经过适当构造即可证明.
其实第一步, 意识到与非能实现所有位运算可能就不容易......
typedef long long ll;
const int N = 1e3, K = 60;
ll v[K], a[N];
bool f[K];
int k, tot;
ll cal(ll x)
{
ll s = 1LL<<(tot-1), ans = 0, y = 0;
Rep (i, 0, tot) {
if ((y | v[i]) <= x) {
ans |= s;
y |= v[i];
}
s >>= 1;
}
return ans + (y != x);
}
int main()
{
int n;
ll l, r;
scanf("%d%d%lld%lld", &n, &k, &l, &r);
Rep (i, 0, n) scanf("%lld", &a[i]);
for (ll s = 1LL<<(k-1), i = k-1; s; s >>= 1, --i) {
if (f[i]) continue;
ll x = (1LL<<k)-1;
Rep (j, 0, n) x &= a[j] & s ? a[j] : ~a[j];
for (ll t = s, j = i; j >= 0; t >>= 1, --j)
if (x & t) f[j] = true;
v[tot++] = x;
}
printf("%lld\n", cal(r+1) - cal(l));
return 0;
}