Recuento de arreglos de suma máxima de tamaño N con elementos en el rango [0, 2^K – 1] y Bitwise AND igual a 0

Dados dos números enteros positivos N y K , la tarea es encontrar el número de arreglos de tamaño N tal que cada elemento del arreglo se encuentre en el rango [0, 2 ^K – 1] con la suma máxima del elemento del arreglo que tenga AND bit a bit de todos los arreglos elementos 0 .

Ejemplos:

Entrada: N = 2 K = 2
Salida: 4
Explicación:
Los arreglos posibles con suma máxima que tienen el AND bit a bit de todos los elementos del arreglo como 0 {0, 3}, {3, 0}, {1, 2}, {2, 1}. El conteo de dicha array es 4.

Entrada: N = 5 K = 6 
Salida: 15625 

Enfoque: El problema dado se puede resolver observando el hecho de que como el AND Bitwise de la array generada debe ser 0 , entonces para cada i en el rango [0, K – 1] debe haber al menos 1 elemento con un i ^-ésimo bit igual a 0 en su representación binaria . Por lo tanto, para maximizar la suma de la array , es óptimo tener exactamente 1 elemento con el i ^-ésimo bit sin establecer.

Por lo tanto, para cada uno de los K bits, hay ^N C ₁ formas de desactivarlo en 1 elemento de array. Por lo tanto, la cuenta resultante de una array que tiene la suma máxima viene dada por N ^K .

A continuación se muestra la implementación del enfoque:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the value of X to
// the power Y
int power(int x, unsigned int y)
{
    // Stores the value of X^Y
    int res = 1;
 
    while (y > 0) {
 
        // If y is odd, multiply x
        // with result
        if (y & 1)
            res = res * x;
 
        // Update the value of y and x
        y = y >> 1;
        x = x * x;
    }
 
    // Return the result
    return res;
}
 
// Function to count number of arrays
// having element over the range
// [0, 2^K - 1] with Bitwise AND value
// 0 having maximum possible sum
void countArrays(int N, int K)
{
    // Print the value of N^K
    cout << int(power(N, K));
}
 
// Driver Code
int main()
{
    int N = 5, K = 6;
    countArrays(N, K);
 
    return 0;
}

// Java program for the above approach
public class GFG
{
 
// Function to find the value of X to
// the power Y
static int power(int x, int y)
{
   
    // Stores the value of X^Y
    int res = 1;
 
    while (y > 0) {
 
        // If y is odd, multiply x
        // with result
        if (y%2!=0)
            res = res * x;
 
        // Update the value of y and x
        y = y >> 1;
        x = x * x;
    }
 
    // Return the result
    return res;
}
 
// Function to count number of arrays
// having element over the range
// [0, 2^K - 1] with Bitwise AND value
// 0 having maximum possible sum
static void countArrays(int N, int K)
{
   
    // Print the value of N^K
   System.out.println((int)(power(N, K)));
}
 
 
// Driver Code
public static void main(String args[])
{
    int N = 5, K = 6;
    countArrays(N, K);
}
}
 
// This code is contributed by SoumikMondal

# Python Program for the above approach
 
# Function to find the value of X to
# the power Y
def power(x, y):
    # Stores the value of X^Y
    res = 1
 
    while (y > 0):
 
        # If y is odd, multiply x
        # with result
        if (y & 1):
            res = res * x
 
        # Update the value of y and x
        y = y >> 1
        x = x * x
 
    # Return the result
    return res
 
# Function to count number of arrays
# having element over the range
# [0, 2^K - 1] with Bitwise AND value
# 0 having maximum possible sum
def countArrays(N, K):
    # Print the value of N^K
    print(power(N, K))
 
 
# Driver Code
 
N = 5;
K = 6;
countArrays(N, K)
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the value of X to
// the power Y
static int power(int x, int y)
{
     
    // Stores the value of X^Y
    int res = 1;
 
    while (y > 0)
    {
         
        // If y is odd, multiply x
        // with result
        if (y % 2 != 0)
            res = res * x;
 
        // Update the value of y and x
        y = y >> 1;
        x = x * x;
    }
 
    // Return the result
    return res;
}
 
// Function to count number of arrays
// having element over the range
// [0, 2^K - 1] with Bitwise AND value
// 0 having maximum possible sum
static void countArrays(int N, int K)
{
     
    // Print the value of N^K
    Console.WriteLine((int)(power(N, K)));
}
 
// Driver Code
public static void Main()
{
    int N = 5, K = 6;
     
    countArrays(N, K);
}
}
 
// This code is contributed by subhammahato348

<script>
        // JavaScript Program for the above approach
 
 
        // Function to find the value of X to
        // the power Y
        function power(x, y) {
            // Stores the value of X^Y
            let res = 1;
 
            while (y > 0) {
 
                // If y is odd, multiply x
                // with result
                if (y & 1)
                    res = res * x;
 
                // Update the value of y and x
                y = y >> 1;
                x = x * x;
            }
 
            // Return the result
            return res;
        }
 
        // Function to count number of arrays
        // having element over the range
        // [0, 2^K - 1] with Bitwise AND value
        // 0 having maximum possible sum
        function countArrays(N, K) {
            // Print the value of N^K
            document.write(power(N, K));
        }
 
        // Driver Code
 
        let N = 5, K = 6;
        countArrays(N, K);
 
    // This code is contributed by Potta Lokesh
 
    </script>

15625

Complejidad temporal: O(log K)
Espacio auxiliar: O(1)