二进制位运算相关的计数问题——巧用高维前缀和：0922T2

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133183403

http://cplusoj.com/d/senior/p/SS230922B

在 https://blog.csdn.net/zhangtingxiqwq/article/details/133176573 当中，我们大致对题目进行了转化。

对于询问 $k$ ，我们现在要求所有 $a(i,j)$ 的异或和，满足 $k\&(i|j)=(i|j)$

对于这个东西，有个常见的套路，叫高维前缀和

首先 $i|j$ 的合法 $k$ 必然为 $i|j$ ，而 $i|j$ 的所有补集都是合法的，这个是可以用高维前缀和做的。

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		a[i][j] = rng.gen(aw);		
		s[i|j]^=a[i][j]; 
	}
}
for(int k=0; k<=22; ++k) {
	for(int i=0; i<(1ll<<23); ++i)
		if((i&(1ll<<k))) {
			s[i]^=s[i-(1ll<<k)]; 
		}
}

unsigned long long res = 0;
for (int i = 1; i <= q; i++) {
	unsigned long long j=rng.gen(kw); 
	j&=(unsigned long long)((1ll<<23)-1);
	res ^= (unsigned long long)i * s[j];
}
printf("%llu\n", res);