自动搬运

查看原文

来自洛谷，原作者为

	Link_Cut_Y 菜就多练

搬运于2025-08-24 22:56:21，当前版本为作者最后更新于2024-03-23 15:10:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

发现异或拆位后各位互不影响。因此考虑拆位。

不妨设 $f_{i, j, k, l}$ 表示到了 $(i, j)$，前面的所有数第 $k$ 位的异或和为 $l$，其概率为多少。不难得到转移：

$$f_{i, j, k, l} \leftarrow (f_{i - 1, j, k, l_1} + f_{i, j - 1, k, l_2}) \times \dfrac{1}{2} $$

于是我们在 $O(nm \log V)$ 复杂度下得到了走到 $(n, m)$ 的期望。

接下来考虑撞墙的概率。不妨设 $g_{i, j}$ 表示走到 $(i, j)$ 格子的概率。转移范围为 $1 \sim n + 1$，以及 $1 \sim m + 1$。最终答案就是 $x \times (\sum g_{n +1, i} +\sum g_{i, m + 1})$。这个转移是 $O(nm)$ 的。

因此我们得到了一个 $O(nm \log n)$ 的做法。代码如下：

int qpow(int a, int b = mod - 2, int s = 1) {
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) s = s * a % mod; return s;
}
void dp(int k) {
	rep(i, 1, n) rep(j, 1, m)
		p[i][j][0] = p[i][j][1] = 0;
	p[1][1][(a[1][1] >> k) & 1] = 1;
	rep(i, 1, n) rep(j, 1, m) {
		if (i == 1 and j == 1) continue;
		if ((a[i][j] >> k) & 1) {
			(p[i][j][1] += inv2 * p[i - 1][j][0]) %= mod;
			(p[i][j][0] += inv2 * p[i - 1][j][1]) %= mod;
			(p[i][j][1] += inv2 * p[i][j - 1][0]) %= mod;
			(p[i][j][0] += inv2 * p[i][j - 1][1]) %= mod;
		} else {
			(p[i][j][1] += inv2 * p[i - 1][j][1]) %= mod;
			(p[i][j][0] += inv2 * p[i - 1][j][0]) %= mod;
			(p[i][j][1] += inv2 * p[i][j - 1][1]) %= mod;
			(p[i][j][0] += inv2 * p[i][j - 1][0]) %= mod;
		}
	}
}
int count(int x) {
	dep(i, 30, 0) if ((x >> i) & 1) return i;
}
signed main() {
	read(n, m, x); inv2 = qpow(2);
	rep(i, 1, n) rep(j, 1, m) read(a[i][j]);
	int mx = 0; rep(i, 1, n) rep(j, 1, m)
		mx = max(mx, a[i][j]);
	int sz = count(mx);
	rep(i, 0, sz) dp(i), (ans += (1ll << i) * p[n][m][1]) %= mod;;
	f[1][1] = 1; rep(i, 1, n + 1) rep(j, 1, m + 1) {
		if (i == 1 and j == 1) continue;
		if (j == m + 1) { (f[i][j] += f[i][j - 1] * inv2) %= mod; continue; }
		if (i == n + 1) { (f[i][j] += f[i - 1][j] * inv2) %= mod; continue; }
		if (j != m + 1) (f[i][j] += f[i - 1][j] * inv2) %= mod;
		if (i != n + 1) (f[i][j] += f[i][j - 1] * inv2) %= mod;
	}
	rep(i, 1, m - 1) (ans += x * f[n + 1][i] % mod) %= mod;
	rep(i, 1, n - 1) (ans += x * f[i][m + 1] % mod) %= mod;
	cout << ans << endl; return 0;
}