异或和

[编程题]异或和

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个n*m的网格图，给出小B出现在每个位置的可能性，用一个n*m的01矩阵表示，小B等概率出现在所有1的位置。求小A在每个位置上与小B期望曼哈顿距离的异或和，先把期望取模之后再异或

输入描述:

第一行读入两个整数 n,m (n,m <= 2000)
接下来n行，每行读入一个长度为m的01字符串。

输出描述:

输出一个整数表示答案模 10⁹+7

示例1

输入

1 3
101

输出

说明

小A出现在(1,1)的时候期望曼哈顿距离是1
小A出现在(1,2)的时候期望曼哈顿距离是1
小A出现在(1,3)的时候期望曼哈顿距离是1
答案是这三者的异或和。

算法知识视频讲解

小嗷犬

发表于 2023-08-07 22:00:09

考察知识点：数学、逆元一个点到另一个点的曼哈顿距离可以分解为 xxx 与 yyy 方向上的分量，同一行的点到另一点的 xxx 分量相同，同一列的点到另一点的 yyy 分量相同。因此，我们可以分别枚举每一行和每一列，统计对应的 xxx 分量和 yyy 分量。对于点 (i,j)(i,j)(i,j)，展开全文