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