Подсчет массивов максимальной суммы N-размера с элементами в диапазоне [0, 2^K – 1] и побитовым И, равным 0

Даны два положительных целых числа N и K , задача состоит в том, чтобы найти количество массивов размера N , таких что каждый элемент массива лежит в диапазоне [0, 2 ^K – 1] с максимальной суммой элементов массива, имеющих побитовое И всех массивов элементы 0 .

Примеры:

Input: N = 2 K = 2
Output: 4
Explanation:
The possible arrays with maximum sum having the Bitwise AND of all array element as 0 {0, 3}, {3, 0}, {1, 2}, {2, 1}. The count of such array is 4.

Input: N = 5 K = 6 
Output: 15625 

Подход: Данную проблему можно решить, заметив тот факт, что поскольку побитовое И сгенерированного массива должно быть равно 0 , то для каждого i в диапазоне [0, K – 1] должен быть хотя бы 1 элемент с i ^-м бит равен 0 в его двоичном представлении. Следовательно, чтобы максимизировать сумму массива, оптимально иметь ровно 1 элемент с неустановленным i ^-м битом.

Следовательно, для каждого из K битов существует ^N C ₁ способов сделать его неустановленным в 1 элементе массива. Следовательно, результирующий счет массива, имеющего максимальную сумму, равен NK.

Ниже приведена реализация подхода:

Временная сложность: O (log K)
Вспомогательное пространство: O(1)