Número de formas de colorear el límite de cada bloque de la tabla M*N

Dada una tabla de M * N . Hay un total de M * N cuadrados de tamaño 1. Tienes que colorear cada lado de todos los cuadrados con 3 colores naranja, azul o negro, de modo que cada cuadrado tenga 2 colores diferentes y cada color debe aparecer dos veces. 
Significa que cada cuadrado tiene cuatro lados, 2 de ellos son naranjas y 2 de ellos son azules o 2 de ellos son naranjas y 2 de ellos son negros o 2 de ellos son azules y 2 de ellos son negros. 
Ejemplos:
 

Entrada: N = 1, M = 1 
Salida: 18 
Explicación: 
Podemos llenar la parte superior del cuadrado y la parte izquierda del cuadrado con cualquiera de los tres colores. Entonces, el número de formas es 3*3. 
Ahora, para llenar la parte derecha e inferior, solo tenemos 2 opciones si la parte superior e izquierda tienen el mismo color. 
Si la parte superior e izquierda tienen un color diferente, podemos usar esos dos colores para llenar la parte derecha e inferior, también tiene 2 opciones. El número de combinación para llenar a la derecha e inferior es 2. 
Una forma total posible de colorear el cuadrado es 3*3*2 = 18
Entrada: N = 3, M = 2 
Salida: 15552

Acercarse:

• Encuentra el número de formas de llenar el lado superior y derecho del rectángulo. El lado superior tiene M unidades y el lado derecho tiene N unidades. Entonces, la cantidad de formas de colorear la parte superior y la derecha del rectángulo es pow (3, M + N) porque cada una tiene 3 opciones.
• Ahora, para llenar el lado inferior e izquierdo de cada cuadrado, tiene 2 opciones para cada cuadrado, entonces el número de formas es pow(2, M * N) .
• El resultado final es:

 Total count = pow(3, M + N ) *  pow(2, M * N)

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

// C++ program to count the number
// of ways to color boundary of
// each block of M*N table.
#include <bits/stdc++.h>
using namespace std;
 
// Function to compute all way to
// fill the boundary of all sides
// of the unit square
int CountWays(int N, int M)
{
    int count = 1;
 
    // Count possible ways to fill
    // all upper and left side of
    // the rectangle M*N
    count = pow(3, M + N);
 
    // Count possible ways to fill
    // all  side of the all squares
    // unit size
    count *= pow(2, M * N);
 
    return count;
}
 
// Driver code
int main()
{
 
    // Number of rows
    int N = 3;
     
    // Number of columns
    int M = 2;
     
    cout << CountWays(N, M);
    return 0;
}

// Java program to count the number
// of ways to color boundary of
// each block of M*N table.
import java.util.*;
 
class GFG{
 
// Function to compute all way to
// fill the boundary of all sides
// of the unit square
static int CountWays(int N, int M)
{
    int count = 1;
 
    // Count possible ways to fill
    // all upper and left side of
    // the rectangle M*N
    count = (int)Math.pow(3, M + N);
 
    // Count possible ways to fill
    // all side of the all squares
    // unit size
    count *= (int)Math.pow(2, M * N);
 
    return count;
}
 
// Driver code
public static void main(String args[])
{
 
    // Number of rows
    int N = 3;
     
    // Number of columns
    int M = 2;
     
    System.out.println(CountWays(N, M));
}
}
 
// This code is contributed by ANKITKUMAR34

# Python3 program to count the number
# of ways to color boundary of
# each block of M*N table.
 
# Function to compute all way to
# fill the boundary of all sides
# of the unit square
def CountWays(N, M):
     
    count = 1
 
    # Count possible ways to fill
    # all upper and left side of
    # the rectangle M*N
    count = pow(3, M + N)
 
    # Count possible ways to fill
    # all side of the all squares
    # unit size
    count *= pow(2, M * N);
 
    return count
 
# Driver code
 
# Number of rows
N = 3
     
# Number of columns
M = 2
     
print(CountWays(N, M))
 
# This code is contributed by ANKITKUMAR34

// C# program to count the number
// of ways to color boundary of
// each block of M*N table.
using System;
 
class GFG{
     
// Function to compute all way to
// fill the boundary of all sides
// of the unit square
static int CountWays(int N, int M)
{
    int count = 1;
 
    // Count possible ways to fill
    // all upper and left side of
    // the rectangle M*N
    count = (int)Math.Pow(3, M + N);
 
    // Count possible ways to fill
    // all side of the all squares
    // unit size
    count *= (int)Math.Pow(2, M * N);
 
    return count;
}
 
// Driver code
static void Main()
{
     
    // Number of rows
    int N = 3;
     
    // Number of columns
    int M = 2;
 
    Console.Write(CountWays(N, M));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// Javascript program to count the number
// of ways to color boundary of
// each block of M*N table.
 
// Function to compute all way to
// fill the boundary of all sides
// of the unit square
function CountWays(N, M)
{
    var count = 1;
 
    // Count possible ways to fill
    // all upper and left side of
    // the rectangle M*N
    count = Math.pow(3, M + N);
 
    // Count possible ways to fill
    // all  side of the all squares
    // unit size
    count *= Math.pow(2, M * N);
 
    return count;
}
 
// Driver code
// Number of rows
var N = 3;
 
// Number of columns
var M = 2;
 
document.write( CountWays(N, M));
 
 
</script>

15552

Complejidad temporal: O(log (m * n))

Espacio Auxiliar: O(1)