Número de formas en que un elemento vuelve a su posición inicial en N intercambios en una array de tamaño K

Dados dos números K y N , la tarea es encontrar el número de formas en que un elemento en la posición i regresa a su posición inicial en una array de longitud K en N pasos, donde, en cada paso, el elemento puede intercambiarse con cualquier otro elemento en K

Ejemplos: 

Entrada: N = 2, K = 5 
Salida: 4 
Explicación: 
Para el K dado, supongamos que hay 5 posiciones 1, 2, 3, 4, 5. Dado que en la pregunta se da que el artículo está en alguna posición inicial B y la respuesta final para todas las B es la misma, supongamos que el elemento está en la posición 1 al principio. Por lo tanto, en 2 pasos (valor N): 
El artículo se puede colocar en la posición 2 y nuevamente en la posición 1. 
El artículo se puede colocar en la posición 3 y nuevamente en la posición 1. 
El artículo se puede colocar en la posición 4 y nuevamente en la posición 1. 
El elemento puede colocarse en la posición 5 y nuevamente en la posición 1. 
Por lo tanto, hay un total de 4 formas. Por lo tanto, la salida es 4.

Entrada: N = 5, K = 5 
Salida: 204 

Planteamiento: La idea para resolver este problema es utilizar el concepto de combinaciones . La idea es que en cada paso, hay K – 1 posibilidades para colocar el elemento en el siguiente lugar. Para implementar esto, se usa una array F[] donde F[i] representa el número de formas de colocar los elementos en la posición 1 para el ‘i’ésimo paso. Como se da que el artículo no pertenece a la persona a la que pertenecía en el paso anterior, por lo tanto, se debe restar el número de formas del paso anterior para cada paso. Por lo tanto, la array F[] se puede llenar como:

F[i] = (K - 1)(i - 1) - F[i - 1]

Finalmente, se devuelve el último elemento de la array F[]. 

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

// C++ program to find the number of ways
// in which an item returns back to its
// initial position in N swaps
// in an array of size K
 
#include <bits/stdc++.h>
using namespace std;
 
#define mod 1000000007
 
// Function to calculate (x^y)%p in O(log y)
long long power(long x, long y)
{
    long p = mod;
 
    // Initialize result
    long res = 1;
 
    // Update x if it is more than or
    // equal to p
    x = x % p;
 
    while (y > 0) {
        // If y is odd, multiply
        // x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        // y = y/2
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Function to return the number of ways
long long solve(int n, int k)
{
    // Base case
    if (n == 1)
        return 0LL;
 
    // Recursive case
    // F(n) = (k-1)^(n-1) - F(n-1).
    return (power((k - 1), n - 1) % mod
            - solve(n - 1, k) + mod)
           % mod;
}
 
// Drivers code
int main()
{
    int n = 4, k = 5;
 
    // Function calling
    cout << solve(n, k);
 
    return 0;
}

// Java program to find the number of ways
// in which an item returns back to its
// initial position in N swaps
// in an array of size K
class GFG{
 
static int mod = 1000000007;
 
// Function to calculate (x^y)%p in O(log y)
public static int power(int x, int y)
{
    int p = mod;
   
    // Initialize result
    int res = 1;
   
    // Update x if it is more than
    // or equal to p
    x = x % p;
   
    while (y > 0)
    {
         
        // If y is odd, multiply
        // x with result
        if ((y & 1) != 0)
            res = (res * x) % p;
   
        // y must be even now
        // y = y/2
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
   
// Function to return the number of ways
public static int solve(int n, int k)
{
     
    // Base case
    if (n == 1)
        return 0;
   
    // Recursive case
    // F(n) = (k-1)^(n-1) - F(n-1).
    return (power((k - 1), n - 1) % mod -
             solve(n - 1, k) + mod) % mod;
}
 
// Driver code
public static void main(String []args)
{
    int n = 4, k = 5;
     
    // Function calling
    System.out.println(solve(n, k));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to find the number of ways
# in which an item returns back to its
# initial position in N swaps
# in an array of size K
 
mod = 1000000007
 
# Function to calculate (x^y)%p in O(log y)
def power(x, y):
 
    p = mod
 
    # Initialize result
    res = 1
 
    # Update x if it is more than or
    # equal to p
    x = x % p
 
    while (y > 0) :
        # If y is odd, multiply
        # x with result
        if (y & 1) != 0 :
            res = (res * x) % p
 
        # y must be even now
        # y = y/2
        y = y >> 1
        x = (x * x) % p
 
    return res
 
# Function to return the number of ways
def solve(n, k):
 
    # Base case
    if (n == 1) :
        return 0
 
    # Recursive case
    # F(n) = (k-1)^(n-1) - F(n-1).
    return (power((k - 1), n - 1) % mod - solve(n - 1, k) + mod) % mod
 
n, k = 4, 5
 
# Function calling
print(solve(n, k))
 
# This code is contributed by divyesh072019

// C# program to find the number of ways
// in which an item returns back to its
// initial position in N swaps
// in an array of size K
using System;
class GFG
{
  
  static int mod = 1000000007;
 
  // Function to calculate
  // (x^y)%p in O(log y)
  public static int power(int x,
                          int y)
  {
    int p = mod;
 
    // Initialize result
    int res = 1;
 
    // Update x if it
    // is more than
    // or equal to p
    x = x % p;
 
    while (y > 0)
    {
      // If y is odd, multiply
      // x with result
      if ((y & 1) != 0)
        res = (res * x) % p;
 
      // y must be even now
      // y = y/2
      y = y >> 1;
      x = (x * x) % p;
    }
    return res;
  }
 
  // Function to return
  // the number of ways
  public static int solve(int n,
                          int k)
  {
    // Base case
    if (n == 1)
      return 0;
 
    // Recursive case
    // F(n) = (k-1)^(n-1) - F(n-1).
    return (power((k - 1), n - 1) % mod -
            solve(n - 1, k) + mod) % mod;
  }
 
  // Driver code
  public static void Main(string []args)
  {
    int n = 4, k = 5;
 
    // Function calling
    Console.Write(solve(n, k));
  }
}
 
// This code is contributed by rutvik_56

<script>
 
    // Javascript program to find the number of ways
    // in which an item returns back to its
    // initial position in N swaps
    // in an array of size K
     
    let mod = 1000000007;
  
    // Function to calculate (x^y)%p in O(log y)
    function power(x, y)
    {
        let p = mod;
 
        // Initialize result
        let res = 1;
 
        // Update x if it is more than or
        // equal to p
        x = x % p;
 
        while (y > 0) {
            // If y is odd, multiply
            // x with result
            if ((y & 1) > 0)
                res = (res * x) % p;
 
            // y must be even now
            // y = y/2
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
 
    // Function to return the number of ways
    function solve(n, k)
    {
        // Base case
        if (n == 1)
            return 0;
 
        // Recursive case
        // F(n) = (k-1)^(n-1) - F(n-1).
        return (power((k - 1), n - 1) % mod
                - solve(n - 1, k) + mod)
               % mod;
    }
     
    let n = 4, k = 5;
  
    // Function calling
    document.write(solve(n, k));
     
</script>

52

Complejidad de tiempo: O (n), ya que estamos usando llamadas recursivas para atravesar n veces.
Espacio auxiliar: O (n), ya que estamos usando espacio adicional para una pila recursiva para nuestras llamadas recursivas.