Contar arreglos de longitud N hechos de los primeros M números naturales cuyos subarreglos se pueden hacer palindrómicos reemplazando menos de la mitad de sus elementos

Dados dos enteros N y M , la tarea es encontrar el recuento de arreglos de tamaño N con elementos del rango [1, M] en el que todos los subarreglos de longitud mayor que 1 se pueden hacer palindrómicos reemplazando menos de la mitad de sus elementos es decir, piso (longitud/2) .

Ejemplos: 

Entrada: N = 2, M = 3
Salida: 6
Explicación:
Hay 9 arrays posibles de longitud 2 usando valores de 1 a 3, es decir, [1, 1], [1, 2], [1, 3], [2, 1 ][2, 2], [2, 3], [3, 1], [3, 2], [3, 3].
Todas estas arrays excepto [1, 1], [2, 2] y [3, 3] tienen subarreglos de longitud superior a 1, lo que requiere 1 operación para convertirlos en palíndromos. Entonces la respuesta requerida es 9 – 3 = 6.

Entrada: N = 5, M = 10
Salida: 30240

Enfoque: El problema se puede resolver con base en las siguientes observaciones:

• Es posible que el número máximo permitido de operaciones requeridas para convertir una array en un palíndromo sea floor(size(array)/2) .
• Se puede observar que al elegir un subarreglo, comenzando y terminando con el mismo valor, el número de operaciones necesarias para convertirlo en un palíndromo será menor que piso (tamaño del subarreglo)/2 .
• Por lo tanto, la tarea se reduce a encontrar el número de arreglos de tamaño N usando valores enteros en el rango [1, M] , que no contienen ningún elemento duplicado, lo que se puede hacer fácilmente al encontrar la permutación de M con N , es decir, Mp _N , que es igual a M * (M – 1) * (M – 2) * … * (M – N + 1).

Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable entera, digamos ans = 1 .
2. Recorra desde i = 0 a N – 1 y actualice ans como ans = ans * (Mi)
3. Escriba ans como la respuesta.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// Function to find the number of arrays
// following the given condition
void noOfArraysPossible(ll N, ll M)
{
    // Initialize answer
    ll ans = 1;
 
    // Calculate nPm
    for (ll i = 0; i < N; ++i) {
        ans = ans * (M - i);
    }
 
    // Print ans
    cout << ans;
}
 
// Driver Code
int main()
{
 
    // Given N and M
    ll N = 2, M = 3;
 
    // Function Call
    noOfArraysPossible(N, M);
 
    return 0;
}

// Java program for the above approach
class GFG
{
 
// Function to find the number of arrays
// following the given condition
static void noOfArraysPossible(int N, int M)
{
    // Initialize answer
    int ans = 1;
 
    // Calculate nPm
    for (int i = 0; i < N; ++i)
    {
        ans = ans * (M - i);
    }
 
    // Print ans
    System.out.print(ans);
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given N and M
    int N = 2, M = 3;
 
    // Function Call
    noOfArraysPossible(N, M);
}
}
 
// This code is contributed by Princi Singh

# Python3 program for the above approach
 
# Function to find the number of arrays
# following the given condition
def noOfArraysPossible(N, M):
     
    # Initialize answer
    ans = 1
  
    # Calculate nPm
    for i in range(N):
        ans = ans * (M - i)
         
    # Print ans
    print(ans)
  
# Driver Code
if __name__ == "__main__" :
     
    # Given N and M
    N = 2
    M = 3
     
    # Function Call
    noOfArraysPossible(N, M)
     
# This code is contributed by jana_sayantan

// C# program to implement
// the above approach 
using System;
 
class GFG{
      
// Function to find the number of arrays
// following the given condition
static void noOfArraysPossible(int N, int M)
{
    // Initialize answer
    int ans = 1;
  
    // Calculate nPm
    for (int i = 0; i < N; ++i)
    {
        ans = ans * (M - i);
    }
  
    // Print ans
    Console.Write(ans);
}
  
// Driver Code
public static void Main()
{
    // Given N and M
    int N = 2, M = 3;
  
    // Function Call
    noOfArraysPossible(N, M);
}
}
 
// This code is contributed by susmitakundugoaldanga

<script>
// javascript program for the above approach   
// Function to find the number of arrays
 
    // following the given condition
    function noOfArraysPossible(N , M)
    {
     
        // Initialize answer
        var ans = 1;
 
        // Calculate nPm
        for (i = 0; i < N; ++i) {
            ans = ans * (M - i);
        }
 
        // Print ans
        document.write(ans);
    }
 
    // Driver Code
     
        // Given N and M
        var N = 2, M = 3;
 
        // Function Call
        noOfArraysPossible(N, M);
 
// This code is contributed by todaysgaurav
</script>

6

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)