小红的异或之和

思路分析

拿到这道题，我们首先要搞清楚：矩阵 $M$ 的所有子矩阵之和到底怎么算？

暴力枚举所有子矩阵肯定不行。那我们换个角度想：每个元素 $M[i][j]$ 会被多少个子矩阵包含？

一个子矩阵由左上角 $(r_1, c_1)$ 和右下角 $(r_2, c_2)$ 确定。如果 $M[i][j]$ 被包含，需要 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 。

用 1-indexed 来算：

$r_1$ 有 $i$ 种选法（ $1$ 到 $i$ ）， $r_2$ 有 $n - i + 1$ 种选法（ $i$ 到 $n$ ）
$c_1$ 有 $j$ 种选法， $c_2$ 有 $n - j + 1$ 种选法

所以 $M[i][j]$ 的贡献次数为 $i \cdot (n+1-i) \cdot j \cdot (n+1-j)$ 。

接下来，注意到贡献次数可以行列分离：定义行权重 $R_i = i \cdot (n+1-i)$ ，列权重 $C_j = j \cdot (n+1-j)$ ，那么：

$ $\text{ans} = \sum_{i=1}^{n}\sum_{j=1}^{n} (a_i \oplus b_j) \cdot R_i \cdot C_j$ $

由于 $a_i, b_j \in \{0, 1\}$ ，异或结果只有两种情况：

$a_i = 1$ ： $a_i \oplus b_j = 1 - b_j$ ，对应 $b_j = 0$ 的列
$a_i = 0$ ： $a_i \oplus b_j = b_j$ ，对应 $b_j = 1$ 的列

因此我们预处理出 $S_0 = \sum_{b_j=0} C_j$ 和 $S_1 = \sum_{b_j=1} C_j$ ，然后对每一行 $i$ ：

若 $a_i = 1$ ，贡献为 $R_i \cdot S_0$
若 $a_i = 0$ ，贡献为 $R_i \cdot S_1$

这样总时间复杂度就从 $O(n^2)$ 降到了 $O(n)$ 。

代码

C++
Java

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const long long MOD = 1e9 + 7;
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];

    // col_weight[j] = (j+1) * (n-j) for 0-indexed
    long long S_col = 0, S_col_1 = 0;
    for(int j = 0; j < n; j++){
        long long w = (long long)(j+1) * (n-j) % MOD;
        S_col = (S_col + w) % MOD;
        if(b[j] == 1){
            S_col_1 = (S_col_1 + w) % MOD;
        }
    }

    long long S_col_0 = (S_col - S_col_1 + MOD) % MOD;

    long long ans = 0;
    for(int i = 0; i < n; i++){
        long long rw = (long long)(i+1) * (n-i) % MOD;
        if(a[i] == 1){
            ans = (ans + rw % MOD * S_col_0 % MOD) % MOD;
        } else {
            ans = (ans + rw % MOD * S_col_1 % MOD) % MOD;
        }
    }

    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final long MOD = 1000000007L;
        int n = sc.nextInt();
        int[] a = new int[n], b = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int i = 0; i < n; i++) b[i] = sc.nextInt();

        long sCol = 0, sCol1 = 0;
        for (int j = 0; j < n; j++) {
            long w = (long)(j + 1) * (n - j) % MOD;
            sCol = (sCol + w) % MOD;
            if (b[j] == 1) sCol1 = (sCol1 + w) % MOD;
        }
        long sCol0 = (sCol - sCol1 + MOD) % MOD;

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long rw = (long)(i + 1) * (n - i) % MOD;
            if (a[i] == 1) {
                ans = (ans + rw * sCol0 % MOD) % MOD;
            } else {
                ans = (ans + rw * sCol1 % MOD) % MOD;
            }
        }
        System.out.println(ans);
    }
}

复杂度分析

时间复杂度： $O(n)$ ，两次遍历数组即可。
空间复杂度： $O(n)$ ，存储输入数组。