Рудольф отправляется в замок. Перед тем, как попасть туда, сотрудники службы безопасности задали ему вопрос:
Задано два числа $$$a$$$ и $$$b$$$ в двоичной системе счисления, их длина равна $$$n$$$. Сколько есть различных способов поменять местами два бита в числе $$$a$$$ (только в $$$a$$$, не в $$$b$$$) так, чтобы побитовое ИЛИ чисел изменилось? Другими словами, пусть $$$c$$$ равно побитовому ИЛИ $$$a$$$ и $$$b$$$, тогда вам нужно найти количество способов поменять местами два бита в $$$a$$$ так, чтобы побитовое ИЛИ не было равно $$$c$$$.
Обратите внимание, что числа могут содержать ведущие нули, так что длина каждого числа равна $$$n$$$.
Побитовое ИЛИ — это бинарная операция. Результат — это такое число, в двоичном представлении которого в каждом разряде стоит единица, если единица находится в двоичной записи хотя бы одного из аргументов. Например, $$$01010_2$$$ ИЛИ $$$10011_2$$$ = $$$11011_2$$$.
К вашему удивлению, вы не Рудольф, и вам не нужно помогать ему$$$\ldots$$$ Вы — сотрудник службы безопасности! Пожалуйста, найдите количество способов поменять местами два бита в $$$a$$$ так, чтобы побитовое ИЛИ изменилось.
Первая строка содержит одно целое число $$$n$$$ ($$$2\leq n\leq 10^5$$$) — количество битов в каждом числе.
Вторая строка содержит число $$$a$$$ длиной $$$n$$$ в двоичной системе счисления.
Третья строка содержит число $$$b$$$ длиной $$$n$$$ в двоичной системе счисления.
Выведите количество возможных способов поменять местами два бита в $$$a$$$ так, чтобы побитовое ИЛИ изменилось.
5
01011
11001
4
6
011000
010011
6
В первом примере вы можете поменять местами биты с такими индексами: $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(3, 4)$$$ и $$$(3, 5)$$$.
Во втором примере вы можете поменять местами биты с такими индексами: $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$ и $$$(3, 6)$$$.
Название |
---|