马蹄钻石题

题目描述:给你一个大的二维数组a[n][n],小的b[m][m],让b在a中滑动，求出b的每一位与a的对应位置的异或，再求和。

思路:不可能暴力枚举n^2*m^2,tle

考虑到每一个b[i][j]在a中的移动轨迹都是一个大小相同的矩形，分析得到左上角a[i][j],和右下角a[n-m+i][n-m+j],求出来这个矩阵的元素个数s=（n-m+1）*(n-m+1),构建一个01数组，用前缀和o(1)的取出a数组每一位有多少个1

#include<bits/stdc++.h>

using namespace std;

// 题目要求的取模常数
const int MOD = 1e9 + 7;

// 题目给定的最大范围为1000，稍微开大一点防止越界
const int MAXN = 1005;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int sum[MAXN][MAXN]; 

int main() {
    // 优化输入输出流，提高读写速度，防止在读入海量数据时超时
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 读入方阵 a (烤鱼)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }

    // 读入方阵 b (短剑)
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> b[i][j];
        }
    }

    long long total_ans = 0;
    
    // 子矩阵的总元素个数（也就是滑动窗口的可能位置数量）
    long long S = 1LL * (n - m + 1) * (n - m + 1);

    // 最大数值为 10^9，2^29 < 10^9 < 2^30，所以枚举 0 到 29 位即可
    for (int p = 0; p < 30; ++p) {
        
        // 1. 针对方阵 a 的第 p 位，构建 0/1 矩阵的二维前缀和
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                int bit = (a[i][j] >> p) & 1; // 提取 a[i][j] 的第 p 位
                // 经典的二维前缀和递推公式
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + bit;
            }
        }

        long long bit_ans = 0; // 记录当前第 p 位产生的总异或为 1 的次数
        
        // 2. 枚举方阵 b 中的每一个元素
        for (int k = 1; k <= m; ++k) {
            for (int l = 1; l <= m; ++l) {
                // 计算 b[k][l] 对应的 a 中子矩阵的左上角 (r1, c1) 和右下角 (r2, c2)
                int r1 = k, c1 = l;
                int r2 = k + n - m, c2 = l + n - m;

                // 利用二维前缀和，O(1) 计算子矩阵中第 p 位为 1 的元素个数
                long long cnt1 = sum[r2][c2] - sum[r1 - 1][c2] - sum[r2][c1 - 1] + sum[r1 - 1][c1 - 1];

                int b_bit = (b[k][l] >> p) & 1; // 提取 b[k][l] 的第 p 位
                
                long long valid_ones = 0;
                if (b_bit == 0) {
                    // 如果 b 这一位是 0，需要 a 这一位是 1 才能异或出 1
                    valid_ones = cnt1;
                } else {
                    // 如果 b 这一位是 1，需要 a 这一位是 0 才能异或出 1
                    // a 这一位是 0 的个数 = 总数 - 是 1 的个数
                    valid_ones = S - cnt1;
                }

                // 累加当前元素在这一位产生的贡献，边加边取模
                bit_ans = (bit_ans + valid_ones) % MOD;
            }
        }

        // 3. 将这一位的总贡献乘上 2^p 权重，并加入最终答案
        long long power = (1LL << p) % MOD; 
        total_ans = (total_ans + bit_ans * power) % MOD;
    }

    // 输出最终答案
    cout << total_ans << "\n";
    return 0;
}
/*代码细节与踩坑排雷说明
	快速 I/O（必备）： 数据量高达 1000×1000，光是读入的数字就有 2×10 
	6
	  个。如果使用普通的 cin / cout 不关同步流，大概率会因为 I/O 耗时导致 Time Limit Exceeded (TLE)。代码中 ios::sync_with_stdio(false); cin.tie(nullptr); 是打消这个隐患的关键。
	
	防止负数取模： 虽然这道题由于 valid_ones 等全是正数累加，不涉及负数取模，但在别的算法题里，如果碰到 (A - B) % MOD，需要写成 (A - B % MOD + MOD) % MOD。这里 S - cnt1 绝对非负，所以可以放心直减。
	
	空间规划： 全局数组 a, b, sum 都声明在堆上，并且类型为 int。1005×1005×4 Bytes≈4 MB。三个数组总共也就十几兆，距离题目 512 MB 的限制非常安全。
	
	位运算的优先级： 代码中提取位时使用了 (a[i][j] >> p) & 1。注意括号一定要加，因为位移运算符 >> 和按位与运算符 & 的优先级低于加减法，如果不加括号极其容易引发逻辑错误。*/