English · Original
Chinese · Translation
Formal · Original
Rudolf is on his way to the castle. Before getting into the castle, the security staff asked him a question:
Given two binary numbers $a$ and $b$ of length $n$. How many different ways of swapping two digits in $a$ (only in $a$, not $b$) so that bitwise OR of these two numbers will be changed? In other words, let $c$ be the bitwise OR of $a$ and $b$, you need to find the number of ways of swapping two bits in $a$ so that bitwise OR will not be equal to $c$.
Note that binary numbers can contain leading zeros so that length of each number is exactly $n$.
[Bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) is a binary operation. A result is a binary number which contains a one in each digit if there is a one in at least one of the two numbers. For example, $01010_2$ _OR_ $10011_2$ = $11011_2$.
Well, to your surprise, you are not Rudolf, and you don't need to help him$\ldots$ You are the security staff! Please find the number of ways of swapping two bits in $a$ so that bitwise OR will be changed.
## Input
The first line contains one integer $n$ ($2\leq n\leq 10^5$) — the number of bits in each number.
The second line contains a binary number $a$ of length $n$.
The third line contains a binary number $b$ of length $n$.
## Output
Print the number of ways to swap two bits in $a$ so that bitwise OR will be changed.
[samples]
## Note
In the first sample, you can swap bits that have indexes $(1, 4)$, $(2, 3)$, $(3, 4)$, and $(3, 5)$.
In the second example, you can swap bits that have indexes $(1, 2)$, $(1, 3)$, $(2, 4)$, $(3, 4)$, $(3, 5)$, and $(3, 6)$.
Rudolf 正在前往城堡的路上。在进入城堡之前，安保人员向他提出了一个问题：
给定两个长度为 $n$ 的二进制数 $a$ 和 $b$。有多少种不同的方式可以交换 $a$ 中的两个数字（仅在 $a$ 中交换，不在 $b$ 中），使得这两个数的按位或结果发生改变？换句话说，令 $c$ 为 $a$ 和 $b$ 的按位或，你需要找出交换 $a$ 中两个比特的方式数，使得新的按位或结果不等于 $c$。
注意，二进制数可能包含前导零，因此每个数的长度恰好为 $n$。
按位或是一种二元运算，其结果是一个二进制数，其中每一位为 1 当且仅当至少有一个输入数在该位上为 1。例如，$01010_2$ _OR_ $10011_2$ = $11011_2$。
令人惊讶的是，你并不是 Rudolf，也不需要帮助他$dots.h$ 你就是安保人员！请找出交换 $a$ 中两个比特的方式数，使得按位或结果发生改变。
第一行包含一个整数 $n$ ($2 lt.eq n lt.eq 10^5$) —— 每个数的比特数。
第二行包含一个长度为 $n$ 的二进制数 $a$。
第三行包含一个长度为 $n$ 的二进制数 $b$。
请输出交换 $a$ 中两个比特使得按位或结果发生改变的方式数。
在第一个样例中，你可以交换索引为 $(1, 4)$、$(2, 3)$、$(3, 4)$ 和 $(3, 5)$ 的比特。
在第二个样例中，你可以交换索引为 $(1, 2)$、$(1, 3)$、$(2, 4)$、$(3, 4)$、$(3, 5)$ 和 $(3, 6)$ 的比特。
## Input
第一行包含一个整数 $n$ ($2 lt.eq n lt.eq 10^5$) —— 每个数的比特数。第二行包含一个长度为 $n$ 的二进制数 $a$。第三行包含一个长度为 $n$ 的二进制数 $b$。
## Output
请输出交换 $a$ 中两个比特使得按位或结果发生改变的方式数。
[samples]
## Note
在第一个样例中，你可以交换索引为 $(1, 4)$、$(2, 3)$、$(3, 4)$ 和 $(3, 5)$ 的比特。在第二个样例中，你可以交换索引为 $(1, 2)$、$(1, 3)$、$(2, 4)$、$(3, 4)$、$(3, 5)$ 和 $(3, 6)$ 的比特。
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 10^5 $.
Let $ a = (a_1, a_2, \dots, a_n) \in \{0,1\}^n $, $ b = (b_1, b_2, \dots, b_n) \in \{0,1\}^n $ be binary strings of length $ n $.
Let $ c = (c_1, c_2, \dots, c_n) $, where $ c_i = a_i \lor b_i $ for all $ i \in \{1, \dots, n\} $, be the bitwise OR of $ a $ and $ b $.
Let $ S $ be the set of all unordered pairs $ \{i, j\} $ with $ 1 \leq i < j \leq n $, representing possible swaps of bits in $ a $.
For a swap $ \{i, j\} $, let $ a' $ be the result of swapping $ a_i $ and $ a_j $ in $ a $, and let $ c' = a' \lor b $ be the new bitwise OR.
**Constraints**
- $ a_i, b_i \in \{0,1\} $ for all $ i \in \{1, \dots, n\} $
- Swaps are performed only on $ a $, not on $ b $
**Objective**
Count the number of unordered pairs $ \{i, j\} $ such that $ c' \neq c $, i.e.,
$$
\left| \left\{ \{i,j\} \mid 1 \leq i < j \leq n,\ a_i \lor b_i \neq a'_i \lor b_i \ \lor \ a_j \lor b_j \neq a'_j \lor b_j \right\} \right|
$$
where $ a'_i = a_j $, $ a'_j = a_i $, and $ a'_k = a_k $ for $ k \neq i,j $.
API Response (JSON)
{
"problem": {
"name": "B. The Bits",
"description": {
"content": "Rudolf is on his way to the castle. Before getting into the castle, the security staff asked him a question: Given two binary numbers $a$ and $b$ of length $n$. How many different ways of swapping tw",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1017B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Rudolf is on his way to the castle. Before getting into the castle, the security staff asked him a question:\n\nGiven two binary numbers $a$ and $b$ of length $n$. How many different ways of swapping tw...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Rudolf 正在前往城堡的路上。在进入城堡之前，安保人员向他提出了一个问题：\n\n给定两个长度为 $n$ 的二进制数 $a$ 和 $b$。有多少种不同的方式可以交换 $a$ 中的两个数字（仅在 $a$ 中交换，不在 $b$ 中），使得这两个数的按位或结果发生改变？换句话说，令 $c$ 为 $a$ 和 $b$ 的按位或，你需要找出交换 $a$ 中两个比特的方式数，使得新的按位或结果不等于 $c$。\n...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^5 $. \nLet $ a = (a_1, a_2, \\dots, a_n) \\in \\{0,1\\}^n $, $ b = (b_1, b_2, \\dots, b_n) \\in \\{0,1\\}^n $ be binary strings of length $ n...",
"is_translate": false,
"language": "Formal"
}
]
}