解题思路

题目要求计算 $n \times n$ 矩阵 $G$ （其中 $G[i][j] = P_i \oplus Q_j$ ）的所有连续子矩阵的元素和，并对 $10^9+7$ 取模。

统计单个元素的贡献次数
对于矩阵中位于第 $i$ 行、第 $j$ 列的元素 $G[i][j]$ （下标从 $1$ 开始），它被包含在多少个连续子矩阵中？
选择子矩阵的起始行和结束行时，行范围必须包含第 $i$ 行，共有 $i \times (n - i + 1)$ 种选择；同理，列范围有 $j \times (n - j + 1)$ 种选择。

题目内容

给定两个长度均为 $n$ 的二进制序列 $P$ 和 $Q$ ，序列中的元素仅包含 $0$ 或 $1$ 。

构造一个 $n \times n$ 的矩阵 $G$ ，其中第 $i$ 行第 $j$ 列的元素定义为 $G[i][j] = P_i \oplus Q_j$ （ $\oplus$ 表示按位异或运算）。

现需要计算矩阵 $G$ 中所有可能的子矩阵的元素值之和。一个子矩阵是指由矩阵中连续若干行与连续若干列相交所构成的区域。由于答案可能很大，请输出结果对 $10^9+7$ 取模后的值。

约束条件：序列长度 $n$ 不超过 $2 \times 10^5$ ，序列中的所有元素均为 $0$ 或 $1$ 。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写

选择提交后点击「开始AI分析」