P10267

Link_Cut_Y · 2024-03-23 15:10:28 · 题解

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

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

于是我们在 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;
}