Dados dos enteros, N y K, la tarea es encontrar el número de permutaciones de números de 0 a N – 1, de modo que haya al menos K posiciones en el arreglo tal que arr[i] = i ( 0 <= i < N ). Como la respuesta puede ser muy grande, calcule el resultado módulo 10^9+7.
Ejemplos:
Entrada: N = 4, K = 3
Salida: 1
Explicación: Solo hay una permutación [0, 1, 2, 3] tal que el número de elementos con arr[i] = i es K = 3.Entrada: N = 4, K = 2
Salida: 7
Explicación: Hay 7 permutaciones que satisfacen la condición que son las siguientes:
- [0, 1, 2, 3]
- [0, 1, 3, 2]
- [0, 3, 2, 1]
- [0, 2, 1, 3]
- [3, 1, 2, 0]
- [2, 1, 0, 3]
- [1, 0, 2, 3]
Enfoque ingenuo: la idea básica para resolver el problema es encontrar primero la permutación de la array.
Siga los pasos para resolver el problema:
- Encuentre recursivamente todas las permutaciones posibles y luego,
- Compruebe para cada uno de ellos si está siguiendo la condición o no.
- Mantenga un contador basado en eso e increméntelo cuando la permutación actual satisfaga la condición.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Recursive function to get the
// all permutations of current array
void getPermutations(vector<int>& arr,
int index, int k,
int& ans)
{
// Base condition if current index is
// greater than or equal to array size
if (index >= arr.size()) {
// Initialising the variable count
int count = 0;
// Counting the number of positions
// with arr[i] = i in the array
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == i) {
count++;
}
}
// If count is greater than
// or equal to k then
// increment the ans
if (count >= k) {
ans++;
}
return;
}
// Iterating over the array arr
for (int i = index; i < arr.size(); i++) {
// Swapping current index with I
swap(arr[index], arr[i]);
// Calling recursion for current
// condition
getPermutations(arr, index + 1, k, ans);
// Resetting the swapped position.
swap(arr[index], arr[i]);
}
}
int numberOfPermutations(long long n,
long long k)
{
// Initializing the variables
//'mod' and 'ans'.
int mod = 1e9 + 7;
int ans = 0;
// Initializing the array 'arr'.
vector<int> arr;
// Pushing numbers in the array.
for (int i = 0; i < n; i++) {
arr.push_back(i);
}
// Calling recursive function 'getPermutations'
getPermutations(arr, 0, k, ans);
// Returning 'ans'.
return ans % mod;
}
// Driver Code
int main()
{
long long N = 4;
long long K = 2;
cout << numberOfPermutations(N, K);
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
class GFG {
static int ans = 0;
// Recursive function to get the
// all permutations of current array
static void getPermutations(Vector<Integer> arr,
int index, long k)
{
// Base condition if current index is
// greater than or equal to array size
if (index >= arr.size()) {
// Initialising the variable count
int count = 0;
// Counting the number of positions
// with arr[i] = i in the array
for (int i = 0; i < arr.size(); i++) {
if (arr.get(i) == i) {
count++;
}
}
// If count is greater than
// or equal to k then
// increment the ans
if (count >= k) {
ans++;
}
return;
}
// Iterating over the array arr
for (int i = index; i < arr.size(); i++) {
// Swapping current index with I
int temp = arr.get(index);
arr.set(index, arr.get(i));
arr.set(i, temp);
// Calling recursion for current
// condition
getPermutations(arr, index + 1, k);
// Resetting the swapped position.
temp = arr.get(index);
arr.set(index, arr.get(i));
arr.set(i, temp);
}
}
static int numberOfPermutations(long n,
long k)
{
// Initializing the variables
//'mod' and 'ans'.
int mod = 1000000000 + 7;
// Initializing the array 'arr'.
Vector<Integer> arr = new Vector<Integer>();
// Pushing numbers in the array.
for (int i = 0; i < n; i++) {
arr.add(i);
}
// Calling recursive function 'getPermutations'
getPermutations(arr, 0, k);
// Returning 'ans'.
return ans % mod;
}
// Driver Code
public static void main (String[] args) {
long N = 4;
long K = 2;
System.out.println(numberOfPermutations(N, K));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the approach # Recursive function to get the # all permutations of current array ans = 0 def getPermutations(arr, index, k): global ans # Base condition if current index is # greater than or equal to array size if (index >= len(arr)): # Initialising the variable count count = 0 # Counting the number of positions # with arr[i] = i in the array for i in range(len(arr)): if (arr[i] == i): count += 1 # If count is greater than # or equal to k then # increment the ans if (count >= k): ans += 1 return # Iterating over the array arr for i in range(index, len(arr)): # Swapping current index with I temp = arr[index] arr[index] = arr[i] arr[i] = temp # Calling recursion for current # condition getPermutations(arr, index + 1, k) # Resetting the swapped position. temp = arr[index] arr[index] = arr[i] arr[i] = temp def numberOfPermutations(n, k): # Initializing the variables #'mod' and 'ans'. mod = 1e9 + 7 # Initializing the array 'arr'. arr = [] # Pushing numbers in the array. for i in range(n): arr.append(i) # Calling recursive function 'getPermutations' getPermutations(arr, 0, k) # Returning 'ans'. return int(ans % mod) # Driver Code N = 4 K = 2 print(numberOfPermutations(N, K)) # This code is contributed by shinjanpatra
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int ans = 0;
// Recursive function to get the
// all permutations of current array
static void getPermutations(List<int> arr,
int index, long k)
{
// Base condition if current index is
// greater than or equal to array size
if (index >= arr.Count) {
// Initialising the variable count
int count = 0;
// Counting the number of positions
// with arr[i] = i in the array
for (int i = 0; i < arr.Count; i++) {
if (arr[i] == i) {
count++;
}
}
// If count is greater than
// or equal to k then
// increment the ans
if (count >= k) {
ans++;
}
return;
}
// Iterating over the array arr
for (int i = index; i < arr.Count; i++) {
// Swapping current index with I
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
// Calling recursion for current
// condition
getPermutations(arr, index + 1, k);
// Resetting the swapped position.
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
static int numberOfPermutations(long n,
long k)
{
// Initializing the variables
//'mod' and 'ans'.
int mod = 1000000000 + 7;
// Initializing the array 'arr'.
List<int> arr = new List<int>();
// Pushing numbers in the array.
for (int i = 0; i < n; i++) {
arr.Add(i);
}
// Calling recursive function 'getPermutations'
getPermutations(arr, 0, k);
// Returning 'ans'.
return ans % mod;
}
// Driver Code
public static void Main()
{
long N = 4;
long K = 2;
Console.Write(numberOfPermutations(N, K));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Recursive function to get the
// all permutations of current array
let ans = 0;
function getPermutations(arr, index, k)
{
// Base condition if current index is
// greater than or equal to array size
if (index >= arr.length) {
// Initialising the variable count
let count = 0;
// Counting the number of positions
// with arr[i] = i in the array
for (let i = 0; i < arr.length; i++) {
if (arr[i] == i) {
count++;
}
}
// If count is greater than
// or equal to k then
// increment the ans
if (count >= k) {
ans++;
}
return;
}
// Iterating over the array arr
for (let i = index; i < arr.length; i++) {
// Swapping current index with I
let temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
// Calling recursion for current
// condition
getPermutations(arr, index + 1, k);
// Resetting the swapped position.
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
function numberOfPermutations(n,k)
{
// Initializing the variables
//'mod' and 'ans'.
let mod = 1e9 + 7;
// Initializing the array 'arr'.
let arr = [];
// Pushing numbers in the array.
for (let i = 0; i < n; i++) {
arr.push(i);
}
// Calling recursive function 'getPermutations'
getPermutations(arr, 0, k);
// Returning 'ans'.
return ans % mod;
}
// Driver Code
let N = 4;
let K = 2;
document.write(numberOfPermutations(N, K));
// This code is contributed by shinjanpatra
</script>
Producción
7
Complejidad de tiempo: O(N * N!)
- Para encontrar recursivamente todas las permutaciones, ¡habrá N! llamadas recursivas,
- Y para cada llamada, habrá un bucle en ejecución con N iteraciones.
- Por lo tanto, la complejidad temporal total será O(N * N!).
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea de resolver el problema de manera eficiente es contar los desarreglos de la array.
Siga los pasos para resolver el problema:
- Primero fije las posiciones en la array de manera que arr[i] != i , Digamos que hay ‘ M ‘ tales posiciones. (0 <= M <= N – K)
- Cuente el número de permutaciones con M fijo para eso, y simplemente elija los índices que tienen el arr[i] !=i
- Encuentra esto usando la fórmula de combinación simple NCM .
- Luego, construya una permutación para los índices elegidos de modo que para cada índice elegido, arr[i] !=i , esto no sea más que los derangements , y encuentre esto mediante una búsqueda exhaustiva.
- Luego haga el trabajo de casos para encontrar los trastornos de acuerdo con el valor de K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Driver function to get the
// modular addition.
int add(long long a, long long b)
{
int mod = 1e9 + 7;
return ((a % mod) + (b % mod)) % mod;
}
// Driver function to get the
// modular multiplication.
int mul(long long a, long long b)
{
int mod = 1e9 + 7;
return ((a % mod) * 1LL * (b % mod)) % mod;
}
// Driver function to get the
// modular binary exponentiation.
int bin_pow(long long a, long long b)
{
int mod = 1e9 + 7;
a %= mod;
long long res = 1;
while (b > 0) {
if (b & 1) {
res = res * 1LL * a % mod;
}
a = a * 1LL * a % mod;
b >>= 1;
}
return res;
}
// Driver function to get the
// modular division.
int reverse(long long x)
{
int mod = 1e9 + 7;
return bin_pow(x, mod - 2);
}
int numberOfPermutations(long long n, long long k)
{
// Updating 'k' with 'n - k'.
k = n - k;
// Initializing the 'ans' by 1.
int ans = 1;
// Condition when 'k' is 1.
if (k == 0 or k == 1) {
return ans;
}
// Adding derangement for 'k' = 2.
ans += mul(mul(n, n - 1), reverse(2));
// Condition when 'k' is 2.
if (k == 2) {
return ans;
}
// Adding derangement for 'k' = 3.
ans += mul(mul(n, mul(n - 1, n - 2)),
reverse(3));
// Condition when 'k' is 3.
if (k == 3) {
return ans;
}
// Adding derangement for 'k' = 4.
int u = mul(n, mul(n - 1, mul(n - 2,
n - 3)));
ans = add(ans, mul(u, reverse(8)));
ans = add(ans, mul(u, reverse(4)));
return ans;
}
// Driver Code
int main()
{
long long N = 4;
long long K = 2;
cout << numberOfPermutations(N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
class GFG {
// Driver function to get the
// modular addition.
static long add(long a, long b)
{
long mod = (int)1e9 + 7;
return ((a % mod) + (b % mod)) % mod;
}
// Driver function to get the
// modular multiplication.
static long mul(long a, long b)
{
long mod = (int)1e9 + 7;
return ((a % mod) * 1 * (b % mod)) % mod;
}
// Driver function to get the
// modular binary exponentiation.
static long bin_pow(long a, long b)
{
long mod = (int)1e9 + 7;
a %= mod;
long res = 1;
while (b > 0) {
if ((b & 1) != 0) {
res = res * 1 * a % mod;
}
a = a * 1 * a % mod;
b >>= 1;
}
return res;
}
// Driver function to get the
// modular division.
static long reverse(long x)
{
long mod = (int)1e9 + 7;
return bin_pow(x, mod - 2);
}
static long numberOfPermutations(long n, long k)
{
// Updating 'k' with 'n - k'.
k = n - k;
// Initializing the 'ans' by 1.
long ans = 1;
// Condition when 'k' is 1.
if (k == 0 || k == 1) {
return ans;
}
// Adding derangement for 'k' = 2.
ans += mul(mul(n, n - 1), reverse(2));
// Condition when 'k' is 2.
if (k == 2) {
return ans;
}
// Adding derangement for 'k' = 3.
ans += mul(mul(n, mul(n - 1, n - 2)),
reverse(3));
// Condition when 'k' is 3.
if (k == 3) {
return ans;
}
// Adding derangement for 'k' = 4.
long u = mul(n, mul(n - 1, mul(n - 2,
n - 3)));
ans = add(ans, mul(u, reverse(8)));
ans = add(ans, mul(u, reverse(4)));
return ans;
}
// Driver Code
public static void main(String args[]) {
long N = 4;
long K = 2;
System.out.print( numberOfPermutations(N, K));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 code for the above approach: # Driver function to get the # modular addition. def add(a, b): mod = int(1e9 + 7) return ((a % mod) + (b % mod)) % mod # Driver function to get the # modular multiplication. def mul(a, b): mod = int(1e9 + 7) return ((a % mod) * (b % mod)) % mod # Driver function to get the # modular binary exponentiation. def bin_pow(a, b): mod = int(1e9 + 7) a %= mod res = 1 while (b > 0): if (b & 1): res = res * a % mod a = a * a % mod b >>= 1 return res # Driver function to get the # modular division. def reverse(x): mod = int(1e9 + 7) return bin_pow(x, mod - 2) def numberOfPermutations(n, k): # Updating 'k' with 'n - k'. k = n - k # Initializing the 'ans' by 1. ans = 1 # Condition when 'k' is 1. if (k == 0 or k == 1): return ans # Adding derangement for 'k' = 2. ans += mul(mul(n, n - 1), reverse(2)) # Condition when 'k' is 2. if (k == 2): return ans # Adding derangement for 'k' = 3. ans += mul(mul(n, mul(n - 1, n - 2)), reverse(3)) # Condition when 'k' is 3. if (k == 3): return ans # Adding derangement for 'k' = 4. u = mul(n, mul(n - 1, mul(n - 2, n - 3))) ans = add(ans, mul(u, reverse(8))) ans = add(ans, mul(u, reverse(4))) return ans # Driver Code if __name__ == "__main__": N = 4 K = 2 print(numberOfPermutations(N, K)) # This code is contributed by rakeshsahni
Producción
7
Complejidad de tiempo : O (Log N)
- Porque, usando la exponencial binaria para obtener el módulo inverso de un número
- la complejidad total del tiempo será O( Log N )
Espacio Auxiliar: O(1)