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)];
}