Número de formas de formar una array con distintos elementos adyacentes

Dados tres enteros N, M y X, la tarea es encontrar el número de formas de formar una array, de modo que todos los números consecutivos de la array sean distintos, y el valor en cualquier índice de la array de 2 a N – 1( Teniendo en cuenta la indexación basada en 1) se encuentra entre 1 y M, mientras que el valor en el índice 1 es X y el valor en el índice N es 1. 
Nota: El valor de X se encuentra entre 1 y M.
Ejemplos: 
 

Entrada: N = 4, M = 3, X = 2 
Salida: 3 
Son posibles las siguientes arrays: 
1) 2, 1, 2, 1 
2) 2, 1, 3, 1 
3) 2, 3, 2, 1
Entrada : N = 2, M = 3, X = 2 
Salida: 1 
La única array posible es: 2, 1

Planteamiento: El problema se puede resolver usando Programación Dinámica . Sea f(i) el número de formas de formar el arreglo hasta el i-ésimo índice, de modo que cada elemento consecutivo del arreglo sea distinto. Sea f(i, Uno) que represente el número de formas de formar el arreglo hasta el i-ésimo índice tal que cada elemento consecutivo del arreglo sea distinto y arr _i = 1. 
De manera similar, sea f(i, Ninguno) quien represente el número de formas de formar el arreglo hasta el i-ésimo índice, tal que cada elemento consecutivo del arreglo sea distinto y arr _i no sea igual a 1.
Se forma la siguiente recurrencia: 
 

f(i, Non-One) = f(i - 1, One) * (M - 1) + f(i - 1, Non-One) * (M - 2)

lo que significa que el número de formas de formar el arreglo hasta el i-ésimo índice con el arreglo _i diferente a 1 se forma usando dos casos: 
 

1. Si el número en el arreglo _{i – 1} es 1, entonces seleccione un número de las opciones (M – 1) para colocarlo en el i ^-ésimo índice, ya que el arreglo _i no es igual a 1.
2. Si el número en la array _{i – 1} no es 1, entonces debemos excluir un número de las opciones (M – 2) , ya que la array _i no es igual a 1 y la array _i ≠ la array _{i – 1} .

De manera similar, f(i, One) = f(i – 1, Non-One) , dado que el número de formas de formar el arreglo hasta el i-ésimo índice con el arreglo _i = 1, es el mismo que el número de formas de formar el arreglo hasta el índice (i – 1) con array _{i – 1} ≠ 1, por lo que en el índice i ^sólo hay una opción. Al final, la respuesta requerida es f(N, One), ya que la array _N debe ser igual a 1.
A continuación, se muestra la implementación del enfoque anterior: 
 

// C++ program to count the number of ways
// to form arrays of N numbers such that the
// first and last numbers are fixed
// and all consecutive numbers are distinct
#include <bits/stdc++.h>
using namespace std;
 
// Returns the total ways to form arrays such that
// every consecutive element is different and each
// element except the first and last can take values
// from 1 to M
int totalWays(int N, int M, int X)
{
 
    // define the dp[][] array
    int dp[N + 1][2];
 
    // if the first element is 1
    if (X == 1) {
 
        // there is only one way to place
        // a 1 at the first index
        dp[0][0] = 1;
    }
    else {
 
        // the value at first index needs to be 1,
        // thus there is no way to place a non-one integer
        dp[0][1] = 0;
    }
 
    // if the first element was 1 then at index 1,
    // only non one integer can be placed thus
    // there are M - 1 ways to place a non one integer
    // at index 2 and 0 ways to place a 1 at the 2nd index
    if (X == 1) {
        dp[1][0] = 0;
        dp[1][1] = M - 1;
    }
 
    // Else there is one way to place a one at
    // index 2 and if a non one needs to be placed here,
    // there are (M - 2) options, i.e
    // neither the element at this index
    // should be 1, neither should it be
    // equal to the previous element
    else {
        dp[1][0] = 1;
        dp[1][1] = (M - 2);
    }
 
    // Build the dp array in bottom up manner
    for (int i = 2; i < N; i++) {
 
        // f(i, one) = f(i - 1, non-one)
        dp[i][0] = dp[i - 1][1];
 
        // f(i, non-one) = f(i - 1, one) * (M - 1) +
        // f(i - 1, non-one) * (M - 2)
        dp[i][1] = dp[i - 1][0] * (M - 1) + dp[i - 1][1] * (M - 2);
    }
 
    // last element needs to be one, so return dp[n - 1][0]
    return dp[N - 1][0];
}
 
// Driver Code
int main()
{
 
    int N = 4, M = 3, X = 2;
    cout << totalWays(N, M, X) << endl;
 
    return 0;
}

// Java program to count the
// number of ways to form
// arrays of N numbers such
// that the first and last
// numbers are fixed and all
// consecutive numbers are
// distinct
import java.io.*;
 
class GFG
{
 
// Returns the total ways to
// form arrays such that every
// consecutive element is
// different and each element
// except the first and last
// can take values from 1 to M
static int totalWays(int N,
                     int M, int X)
{
 
    // define the dp[][] array
    int dp[][] = new int[N + 1][2];
 
    // if the first element is 1
    if (X == 1)
    {
 
        // there is only one
        // way to place a 1
        // at the first index
        dp[0][0] = 1;
    }
    else
    {
 
        // the value at first index
        // needs to be 1, thus there
        // is no way to place a
        // non-one integer
        dp[0][1] = 0;
    }
 
    // if the first element was 1
    // then at index 1, only non
    // one integer can be placed
    // thus there are M - 1 ways
    // to place a non one integer
    // at index 2 and 0 ways to
    // place a 1 at the 2nd index
    if (X == 1)
    {
        dp[1][0] = 0;
        dp[1][1] = M - 1;
    }
 
    // Else there is one way to
    // place a one at index 2
    // and if a non one needs to
    // be placed here, there are
    // (M - 2) options, i.e neither
    // the element at this index
    // should be 1, neither should
    // it be equal to the previous
    // element
    else
    {
        dp[1][0] = 1;
        dp[1][1] = (M - 2);
    }
 
    // Build the dp array
    // in bottom up manner
    for (int i = 2; i < N; i++)
    {
 
        // f(i, one) = f(i - 1,
        // non-one)
        dp[i][0] = dp[i - 1][1];
 
        // f(i, non-one) =
        // f(i - 1, one) * (M - 1) +
        // f(i - 1, non-one) * (M - 2)
        dp[i][1] = dp[i - 1][0] * (M - 1) +
                   dp[i - 1][1] * (M - 2);
    }
 
    // last element needs to be
    // one, so return dp[n - 1][0]
    return dp[N - 1][0];
}
 
// Driver Code
public static void main (String[] args)
{
    int N = 4, M = 3, X = 2;
    System.out.println(totalWays(N, M, X));
}
}
 
// This code is contributed by anuj_67.

# Python 3 program to count the number of ways
# to form arrays of N numbers such that the
# first and last numbers are fixed
# and all consecutive numbers are distinct
 
# Returns the total ways to form arrays such that
# every consecutive element is different and each
# element except the first and last can take values
# from 1 to M
def totalWays(N,M,X):
     
    # define the dp[][] array
    dp = [[0 for i in range(2)] for j in range(N+1)]
 
    # if the first element is 1
    if (X == 1):
         
        # there is only one way to place
        # a 1 at the first index
        dp[0][0] = 1
 
    else:
        # the value at first index needs to be 1,
        # thus there is no way to place a non-one integer
        dp[0][1] = 0
 
    # if the first element was 1 then at index 1,
    # only non one integer can be placed thus
    # there are M - 1 ways to place a non one integer
    # at index 2 and 0 ways to place a 1 at the 2nd index
    if (X == 1):
        dp[1][0] = 0
        dp[1][1] = M - 1
 
    # Else there is one way to place a one at
    # index 2 and if a non one needs to be placed here,
    # there are (M - 2) options, i.e
    # neither the element at this index
    # should be 1, neither should it be
    # equal to the previous element
    else:
        dp[1][0] = 1
        dp[1][1] = (M - 2)
 
    # Build the dp array in bottom up manner
    for i in range(2,N):
        # f(i, one) = f(i - 1, non-one)
        dp[i][0] = dp[i - 1][1]
 
        # f(i, non-one) = f(i - 1, one) * (M - 1) +
        # f(i - 1, non-one) * (M - 2)
        dp[i][1] = dp[i - 1][0] * (M - 1) + dp[i - 1][1] * (M - 2)
 
    # last element needs to be one, so return dp[n - 1][0]
    return dp[N - 1][0]
 
# Driver Code
if __name__ == '__main__':
    N = 4
    M = 3
    X = 2
    print(totalWays(N, M, X))
     
# This code is contributed by
# Surendra_Gangwar

// C# program to count the
// number of ways to form
// arrays of N numbers such
// that the first and last
// numbers are fixed and all
// consecutive numbers are
// distinct
using System;
 
class GFG
{
 
// Returns the total ways to
// form arrays such that every
// consecutive element is
// different and each element
// except the first and last
// can take values from 1 to M
static int totalWays(int N,
                     int M, int X)
{
 
    // define the dp[][] array
    int [,]dp = new int[N + 1, 2];
 
    // if the first element is 1
    if (X == 1)
    {
 
        // there is only one
        // way to place a 1
        // at the first index
        dp[0, 0] = 1;
    }
    else
    {
 
        // the value at first index
        // needs to be 1, thus there
        // is no way to place a
        // non-one integer
        dp[0, 1] = 0;
    }
 
    // if the first element was 1
    // then at index 1, only non
    // one integer can be placed
    // thus there are M - 1 ways
    // to place a non one integer
    // at index 2 and 0 ways to
    // place a 1 at the 2nd index
    if (X == 1)
    {
        dp[1, 0] = 0;
        dp[1, 1] = M - 1;
    }
 
    // Else there is one way to
    // place a one at index 2
    // and if a non one needs to
    // be placed here, there are
    // (M - 2) options, i.e neither
    // the element at this index
    // should be 1, neither should
    // it be equal to the previous
    // element
    else
    {
        dp[1, 0] = 1;
        dp[1, 1] = (M - 2);
    }
 
    // Build the dp array
    // in bottom up manner
    for (int i = 2; i < N; i++)
    {
 
        // f(i, one) = f(i - 1,
        // non-one)
        dp[i, 0] = dp[i - 1, 1];
 
        // f(i, non-one) =
        // f(i - 1, one) * (M - 1) +
        // f(i - 1, non-one) * (M - 2)
        dp[i, 1] = dp[i - 1, 0] * (M - 1) +
                   dp[i - 1, 1] * (M - 2);
    }
 
    // last element needs to be
    // one, so return dp[n - 1][0]
    return dp[N - 1, 0];
}
 
// Driver Code
public static void Main ()
{
    int N = 4, M = 3, X = 2;
    Console.WriteLine(totalWays(N, M, X));
}
}
 
// This code is contributed
// by anuj_67.

<?php
// PHP program to count the
// number of ways to form
// arrays of N numbers such
// that the first and last
// numbers are fixed and all
// consecutive numbers are distinct
 
// Returns the total ways to
// form arrays such that every
// consecutive element is
// different and each element
// except the first and last
// can take values from 1 to M
function totalWays($N, $M, $X)
{
 
    // define the dp[][] array
    $dp = array(array());
 
    // if the first element is 1
    if ($X == 1)
    {
 
        // there is only one
        // way to place a 1
        // at the first index
        $dp[0][0] = 1;
    }
    else
    {
 
        // the value at first
        // index needs to be 1,
        // thus there is no way
        // to place a non-one integer
        $dp[0][1] = 0;
    }
 
    // if the first element was
    // 1 then at index 1, only
    // non one integer can be
    // placed thus there are M - 1
    // ways to place a non one
    // integer at index 2 and 0 ways
    // to place a 1 at the 2nd index
    if ($X == 1)
    {
        $dp[1][0] = 0;
        $dp[1][1] = $M - 1;
    }
 
    // Else there is one way
    // to place a one at index
    // 2 and if a non one needs
    // to be placed here, there
    // are (M - 2) options, i.e
    // neither the element at
    // this index should be 1,
    // neither should it be equal
    // to the previous element
    else
    {
        $dp[1][0] = 1;
        $dp[1][1] = ($M - 2);
    }
 
    // Build the dp array
    // in bottom up manner
    for ($i = 2; $i <$N; $i++)
    {
 
        // f(i, one) =
        // f(i - 1, non-one)
        $dp[$i][0] = $dp[$i - 1][1];
 
        // f(i, non-one) =
        // f(i - 1, one) * (M - 1) +
        // f(i - 1, non-one) * (M - 2)
        $dp[$i][1] = $dp[$i - 1][0] *
                           ($M - 1) +
                     $dp[$i - 1][1] *
                           ($M - 2);
    }
 
    // last element needs to
    // be one, so return dp[n - 1][0]
    return $dp[$N - 1][0];
}
 
// Driver Code
$N = 4; $M = 3; $X = 2;
echo totalWays($N, $M, $X);
 
// This code is contributed
// by anuj_67.
?>

<script>
    // Javascript program to count the
    // number of ways to form
    // arrays of N numbers such
    // that the first and last
    // numbers are fixed and all
    // consecutive numbers are
    // distinct
     
    // Returns the total ways to
    // form arrays such that every
    // consecutive element is
    // different and each element
    // except the first and last
    // can take values from 1 to M
    function totalWays(N, M, X)
    {
 
        // define the dp[][] array
        let dp = new Array(N + 1);
        for(let i = 0; i < N + 1; i++)
        {
            dp[i] = new Array(2);
            for(let j = 0; j < 2; j++)
            {
                dp[i][j] = 0;
            }
        }
 
        // if the first element is 1
        if (X == 1)
        {
 
            // there is only one
            // way to place a 1
            // at the first index
            dp[0][0] = 1;
        }
        else
        {
 
            // the value at first index
            // needs to be 1, thus there
            // is no way to place a
            // non-one integer
            dp[0][1] = 0;
        }
 
        // if the first element was 1
        // then at index 1, only non
        // one integer can be placed
        // thus there are M - 1 ways
        // to place a non one integer
        // at index 2 and 0 ways to
        // place a 1 at the 2nd index
        if (X == 1)
        {
            dp[1][0] = 0;
            dp[1][1] = M - 1;
        }
 
        // Else there is one way to
        // place a one at index 2
        // and if a non one needs to
        // be placed here, there are
        // (M - 2) options, i.e neither
        // the element at this index
        // should be 1, neither should
        // it be equal to the previous
        // element
        else
        {
            dp[1][0] = 1;
            dp[1][1] = (M - 2);
        }
 
        // Build the dp array
        // in bottom up manner
        for (let i = 2; i < N; i++)
        {
 
            // f(i, one) = f(i - 1,
            // non-one)
            dp[i][0] = dp[i - 1][1];
 
            // f(i, non-one) =
            // f(i - 1, one) * (M - 1) +
            // f(i - 1, non-one) * (M - 2)
            dp[i][1] = dp[i - 1][0] * (M - 1) +
                       dp[i - 1][1] * (M - 2);
        }
 
        // last element needs to be
        // one, so return dp[n - 1][0]
        return dp[N - 1][0];
    }
     
    let N = 4, M = 3, X = 2;
    document.write(totalWays(N, M, X));
 
// This code is contributed by divyeshrabadiya07.
</script>

3

Complejidad de tiempo: O(N), donde N es el tamaño de la array