题解 | #异或和#

考察知识点：数学、逆元

一个点到另一个点的曼哈顿距离可以分解为 $xx$ 与 $yy$ 方向上的分量，同一行的点到另一点的 $xx$ 分量相同，同一列的点到另一点的 $yy$ 分量相同。

因此，我们可以分别枚举每一行和每一列，统计对应的 $xx$ 分量和 $yy$ 分量。对于点 $(i,j)(i,j)$，它的期望曼哈顿距离为第 $ii$ 行的 $xx$ 分量与第 $jj$ 列的 $yy$ 分量之和。

然后枚举每个位置的点计算期望曼哈顿距离的异或和即可。

计算期望时注意使用逆元。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 2005
#define MOD 1000000007

int board[N][N], x[N], y[N];
int row[N], col[N];

ll qpw(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    int fenMu = 0;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
        {
            board[i][j] = s[j - 1] - '0';
            fenMu += board[i][j];
            row[i] += board[i][j];
            col[j] += board[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            x[i] += row[j] * abs(i - j);
            x[i] %= MOD;
        }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
        {
            y[i] += col[j] * abs(i - j);
            y[i] %= MOD;
        }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int fenZi = (x[i] + y[j]) % MOD;
            ans ^= fenZi * qpw(fenMu, MOD - 2) % MOD;
        }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}