Recuento de formas de generar una Array con producto de cada fila y columna como 1 o -1

Dados dos números enteros N y M , la tarea es encontrar el número de formas de formar una array de tamaño N * M que consiste solo en 1 o -1, tal que el producto de los números enteros en cada fila y cada columna sea igual a 1 o -1.

Ejemplos:

Entrada: N = 2, M = 2 
Salida: 4 
Explicación:  Las formas posibles de obtener el producto de cada fila y columna como 1 son, 
{{1, 1}, {1, 1}} y {{-1, -1} , {-1, -1}} 
Las formas posibles de obtener el producto de cada fila y columna como -1 son, {{1, -1}, {-1, 1}} y {{-1, 1}, {1 , -1}} Por lo tanto, número de formas = 2 + 2 = 4

Entrada: N = 3, M = 3 
Salida: 32 
Explicación:  Hay 16 formas de obtener el producto como 1 y 16 formas de obtener el producto como -1. Por lo tanto, número de formas = 16 + 16 = 32

Enfoque ingenuo: 
el enfoque más simple para resolver este problema es generar todas las arrays posibles de tamaño N * M y, para cada una de ellas, calcular el producto de todas las filas y columnas y verificar si es 1 o -1. 
Complejidad temporal: O(2 ^N*M ) 
Espacio auxiliar: O(M*N)

Enfoque eficiente:  suponga que las primeras N-1 filas y las primeras M-1 columnas se llenan con 1 o -1. Ahora, el producto de cada fila hasta N-1 filas y cada columna hasta M-1 columnas sería 1 o -1 . Hay un total de 2 ^{(N-1) * (M-1)} Formas de formar una array de tamaño (N-1)*(M-1) llena con 1 o -1. Dependiendo de lo que se necesite como producto de N filas y M columnas, la última fila y columna se pueden llenar en consecuencia.
Siga los pasos para resolver el problema:

• Si N + M es par , 
  Número de arrays posibles para obtener el producto como 1 = 2 ^{(N-1) * (M-1)} 
  Número de arrays posibles para obtener el producto como -1 = 2 ^{(N-1) * (M -1)}
• Si N + M es impar , 
  Número de arrays posibles para obtener el producto como 1 = 2 ^{(N-1) * (M-1)} 
  Número de arrays posibles para obtener el producto como -1 = 0

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

// C++ implementation of
// the above approach
 
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the
// number of possible ways
void Solve(int N, int M)
{
 
    int temp = (N - 1) * (M - 1);
    int ans = pow(2, temp);
 
    // Check if product can be -1
    if ((N + M) % 2 != 0)
        cout << ans;
    else
        cout << 2 * ans;
 
    cout << endl;
}
// Driver Code
int main()
{
    int N = 3;
    int M = 3;
 
    Solve(N, M);
    return 0;
}

// Java implementation of the above approach
import java.util.Arrays;
 
class GFG{
     
// Function to return the
// number of possible ways
static void Solve(int N, int M)
{
    int temp = (N - 1) * (M - 1);
    int ans = (int)(Math.pow(2, temp));
 
    // Check if product can be -1
    if ((N + M) % 2 != 0)
        System.out.print(ans);
    else
        System.out.print(2 * ans);
}
 
// Driver code
public static void main (String[] args)
{
    int N = 3;
    int M = 3;
     
    Solve(N, M);
}
}
 
// This code is contributed by Shubham Prakash

# Python3 program to implement
# the above approach
# Function to return
# possible number of ways
 
 
def Solve(N, M):
    temp = (N - 1) * (M - 1)
    ans = pow(2, temp)
 
    # Check if product can be -1
    if ((N + M) % 2 != 0):
        print(ans)
    else:
        print(2 * ans)
 
        # driver code
if __name__ == '__main__':
    N, M = 3, 3
    Solve(N, M)
 
# This code is contributed by Sri_srajit

// C# implementation of the above approach
using System;
 
class GFG{
     
// Function to return the
// number of possible ways
static void Solve(int N, int M)
{
    int temp = (N - 1) * (M - 1);
    int ans = (int)(Math.Pow(2, temp));
 
    // Check if product can be -1
    if ((N + M) % 2 != 0)
        Console.Write(ans);
    else
        Console.Write(2 * ans);
}
 
// Driver Code
public static void Main(string[] args)
{
    int N = 3;
    int M = 3;
     
    Solve(N, M);
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript program implementation
// of the approach
 
// Function to return the
// number of possible ways
function Solve(N, M)
{
    let temp = (N - 1) * (M - 1);
    let ans = (Math.pow(2, temp));
   
    // Check if product can be -1
    if ((N + M) % 2 != 0)
        document.write(ans);
    else
        document.write(2 * ans);
}
 
// Driver Code
     
       let N = 3;
    let M = 3;
       
    Solve(N, M);
          
</script>

// C implementation of
// the above approach
 
#include<stdio.h>
#include<math.h>
 
// Function to return the
// number of possible ways
void Solve(int N, int M)
{
 
    int temp = (N - 1) * (M - 1);
    int ans = pow(2, temp);
 
    // Check if product can be -1
    if ((N + M) % 2 != 0)
        printf("%d",ans);
    else
       printf("%d",(2*ans));
 
    printf("\n");
}
// Driver Code
void main()
{
    int N = 3;
    int M = 3;
 
    Solve(N, M);
}

32

Complejidad temporal: O(log(N*M)) 
Espacio auxiliar: O(1)