CF2131F Unjust Binary Life

Yuri 有两个长度为 $n$ 的 01 字符串 $a$ 和 $b$，这两个字符串可以定义一个 $n \times n$ 的网格。记 $(i, j)$ 为第 $i$ 行第 $j$ 列的单元格。单元格 $(i, j)$ 的值为 $a_i \oplus b_j$，其中 $\oplus$ 表示按位异或运算。 Yuri 的旅途永远从单元格 $(1, 1)$ 开始。从单元格 $(i, j)$ 出发，她只能向下移动到单元格 $(i+1, j)$ 或者向右移动到单元格 $(i, j+1)$。当且仅当路径上所有单元格——包括起始单元格 $(1, 1)$——的值均为 $0$ 时，她才能沿着这条路径移动。 在她出发之前，她可以进行任意次下列操作。 - 选择一个索引 $1 \le i \le n$，然后翻转 $a_i$ 或者 $b_i$ 的值。也就是说，$1$ 会变为 $0$，而将$0$ 会变为 $1$。网格也会随之改变。 记 $f(x, y)$ 为 Yuri 为了到达单元格 $(x, y)$ 需要进行操作的最小次数，你需要计算出所有 $1 \le x,y \le n$ 对应的 $f(x,y)$ 之和。 注意这 $n^2$ 种情况是独立的，也就是说，在计算每一个 $f(x, y)$ 的时候，$a$ 和 $b$ 的值都为初始状态。

输入数据包含多组测试用例，第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。对于每个测试用例： - 第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 - 第二行包含一个 $01$ 字符串 $a$（$|a| = n, a_i \in \{0,1\}$）。 - 第三行包含一个 $01$ 字符串 $b$（$|b| = n, b_i \in \{0,1\}$）。 输入数据保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

对于每个测试用例，输出一个整数，表示对于所有单元格，所需要的最小操作次数之和。

在第一个测试用例中，$2 \times 2$ 的网格如下所示。 $$ 11 \\ 11 $$ 在初始状态下，Yuri 无法到达任何单元格。 Yuri 可以翻转 $a_1$，然后网格变为： $$ 00 \\ 11 $$ 于是 Yuri 便可以到达单元格 $(1,1)$ 和 $(1,2)$。 另一方面，Yuri 可以翻转 $b_1$，然后网格变为： $$ 01 \\ 01 $$ 于是 Yuri 就可以到达单元格 $(1,1)$ 和 $(2,1)$。 为了到达单元格 $(2,2)$，可以证明 Yuri 必须操作至少两次。比如，她可以翻转 $a_1$，然后翻转 $a_2$，网格变为： $$ 00 \\ 00 $$ 因此，答案是 $1+1+1+2=5$.