Свойства исключающего или
Есть некоторый набор целых положительных чисел (0 может входить) и число M
A1,A2,...,An
Удовлетворяющий следующим свойствам:
A1+A2+...+An = M
A1^A2^...^An = 0
И нужно найти количество наборов таких чисел длины N. Не знаю даже, как подступиться к задаче. Пытался что-то выводить из свойств исключающего или, но ни до чего толкового не дошел
Ответы (1 шт):
Найдём максимальную степень двойки K, такую, что 2^K <= M (т.е. номер старшего единичного бита в M). Тогда в сумме M могут участвовать два бита (нам же нужны парные) с номером K-1, распределённые по N местам. Таких распределений (сочетаний) C(N, 2). Запомним это число P. Если убрать эти два бита, то останется значение M-2^K, продолжим решать для него задачу рекурсивно до младших битов, получим число P'. А объединением их будет произведение количества вариантов Q = P * P'
Однако вместо пары старших битов в сумме может участвовать четвёрка, пара, или ноль битов с номером K-2 и так далее. Поэтому для сборки реального результата нужно учесть все эти варианты.
F(M,K) = [C(N,2)*F(M-2^K,K-1)]+[C[N,4]*F(M-2^K,K-2)]+[C[N,2]*F(M-2^(K-1),K-2)]+[C(N,8)*F(M-2^K,K-3)]+...
| | |
есть два старших бита | |
| |
старших нет, есть четыре вторых |
старших нет, есть два вторых
нет старших и вторых, есть восемь третьих
Для вычисления результата можно создать таблицу размером MxK и заполнять её ряд за рядом.