CWOI S C0314 B 快哭了

题意

U2FsdGVkX19ggnHSs9l9dqPtatqOUgvukzDQ0KjPIDrarT71mVlAHswlOPk45FTs
EjGZ/Wjwt18pxt/5Ww1uBuFHIFqTm9xaClPvpxKNaxJ8JsEgD+ilS1VAnZoMwWLo
pmfSNHbZI0l+BNle8mB0J4gT/TUU5izHdUhZe/Y9DqyTpvzU77vM788RF8et83D8
Ihtkln9wgUQfce3HAKsuqMXA1wYkt4tP52eM5fjlWpVt/oVoVwB5/7RVL1j6SIPB
gUeiduY+JtQGHR0Gx4BEbFu/ZLkltHgc8Ch7uV0T2BRFyhdBKUolfdyxBkpESPnK
2GEjnVz+LTZBdipYnIciyQ==

解析

(i, j) 位置给 (0, 0) 的贡献次数，可以理解成从 (i, j) 开始，每一步可以向左，向上，向左上，不动，在恰好 k 步走到 (0, 0) 的方案数。将横竖分开考虑，相当于每一步可以走也可以不走，即是：$\binom{k}{i} \times \binom{k}{j}$。由于是异或，只需要考虑贡献次数为奇数的，由卢卡斯定理可知，只有满足 $i \operatorname{or} k = k \land j \operatorname{or} k = k$ 的 (i, j) 才会产生贡献，即要求 $(i \operatorname{or} j) \operatorname{or} k = k$，sosdp 预处理一下即可。

实现

constexpr int MAXBIT = 23;
int f[1 << MAXBIT];

void init(int n, int m, int q, int aw, int kw, vector<vector<int> > a) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			f[i | j] ^= a[i][j];
		}
	}
	for (int i = 0; i < MAXBIT; i++) {
		for (int j = 0; j < (1 << MAXBIT); j++) {
			if ((j >> i) & 1) {
				f[j] ^= f[j ^ (1 << i)];
			}
		}
	}
}

int query(int k) {
	return f[k & ((1 << MAXBIT) - 1)];
}