Dados dos valores N y K . Encuentre el número de formas de organizar los N elementos distintos en las cajas de manera que se usen exactamente K (K<N) cajas de las N cajas distintas. La respuesta puede ser muy grande, así que devuelva la respuesta módulo 10 9 + 7.
Nota: 1 <= N <= K <= 10 5 .
Requisitos previos: factorial de un número , calcular nCr % p
Ejemplos:
Entrada: N = 5, k = 5
Salida: 120Entrada: N = 5, k = 3
Salida: 1500
Planteamiento: Usaremos el principio de inclusión-exclusión para contar las formas.
- Supongamos que los cuadros están numerados del 1 al N y ahora tenemos que elegir K cuadros y usarlos. El número de formas de hacer esto es N CK .
- Ahora cualquier elemento puede colocarse en cualquiera de las casillas elegidas, por lo tanto, el número de formas de organizarlos es K N. Pero aquí, podemos contar los arreglos con algunas casillas vacías. Por lo tanto, utilizaremos el principio de inclusión-exclusión para asegurarnos de contar formas con todos los K cuadros llenos con al menos un elemento.
- Entendamos la aplicación del principio de inclusión-exclusión:
- Entonces, de K N maneras, restamos el caso cuando al menos 1 caja (de K) está vacía. Por lo tanto, reste
(K C1 )*((K-1) N ) . - Tenga en cuenta que aquí, los casos en los que exactamente dos casillas están vacías se restan dos veces (una vez cuando elegimos el primer elemento en formas ( K C1 ) y luego cuando elegimos el segundo elemento en formas ( K C1 )).
- Por lo tanto, agregamos estas formas una vez para compensar. Entonces sumamos (K C2 )*((K – 2) N ) .
- De manera similar, aquí debemos agregar el número de formas cuando al menos 3 cajas estaban vacías, y así sucesivamente…
- Entonces, de K N maneras, restamos el caso cuando al menos 1 caja (de K) está vacía. Por lo tanto, reste
- Por lo tanto, el número total de formas:
C++
// C++ program to calculate the
// above formula
#include <bits/stdc++.h>
#define mod 1000000007
#define int long long
using namespace std;
// To store the factorials
// of all numbers
int factorial[100005];
// Function to calculate factorial
// of all numbers
void StoreFactorials(int n)
{
factorial[0] = 1;
for (int i = 1; i <= n; i++)
{
factorial[i] =
(i * factorial[i - 1])
% mod;
}
}
// Calculate x to the power y
// in O(log n) time
int Power(int x, int y)
{
int ans = 1;
while (y > 0) {
if (y % 2 == 1) {
ans = (ans * x) % mod;
}
x = (x * x) % mod;
y /= 2;
}
return ans;
}
// Function to find inverse mod of
// a number x
int invmod(int x)
{
return Power(x, mod - 2);
}
// Calculate (n C r)
int nCr(int n, int r)
{
return (factorial[n]
* invmod((factorial[r]
* factorial[n - r]) % mod))
% mod;
}
int CountWays(int n,int k)
{
StoreFactorials(n);
// Loop to compute the formula
// evaluated
int ans = 0;
for (int i = k; i >= 0; i--)
{
if (i % 2 == k % 2)
{
// Add even power terms
ans = (ans + (Power(i, n)
* nCr(k, i)) % mod)
% mod;
}
else
{
// Subtract odd power terms
ans = (ans + mod - (Power(i, n)
* nCr(k, i)) % mod) % mod;
}
}
// Choose the k boxes which
// were used
ans = (ans * nCr(n, k)) % mod;
return ans;
}
// Driver code
signed main()
{
int N = 5;
int K = 5;
cout << CountWays(N, K) << "\n";
return 0;
}
Java
// Java program to calculate the
// above formula
import java.util.*;
class GFG{
static long mod = 1000000007;
// To store the factorials
// of all numbers
static long factorial[] = new long[100005];
// Function to calculate factorial
// of all numbers
static void StoreFactorials(int n)
{
factorial[0] = 1;
for(int i = 1; i <= n; i++)
{
factorial[i] = (i *
factorial[i - 1]) % mod;
}
}
// Calculate x to the power y
// in O(log n) time
static long Power(long x, long y)
{
long ans = 1;
while (y > 0)
{
if (y % 2 == 1)
{
ans = (ans * x) % mod;
}
x = (x * x) % mod;
y /= 2;
}
return ans;
}
// Function to find inverse mod of
// a number x
static long invmod(long x)
{
return Power(x, mod - 2);
}
// Calculate (n C r)
static long nCr(int n, int r)
{
return (factorial[n] *
invmod((factorial[r] *
factorial[n - r]) % mod)) % mod;
}
static long CountWays(int n,int k)
{
StoreFactorials(n);
// Loop to compute the formula
// evaluated
long ans = 0;
for(int i = k; i >= 0; i--)
{
if (i % 2 == k % 2)
{
// Add even power terms
ans = (ans + (Power(i, n) *
nCr(k, i)) % mod) % mod;
}
else
{
// Subtract odd power terms
ans = (ans + mod - (Power(i, n) *
nCr(k, i)) % mod) % mod;
}
}
// Choose the k boxes which
// were used
ans = (ans * nCr(n, k)) % mod;
return ans;
}
// Driver Code
public static void main (String[] args)
{
int N = 5;
int K = 5;
System.out.print(CountWays(N, K) + "\n");
}
}
// This code is contributed by math_lover
Python3
# Python3 program to calculate the # above formula mod = 1000000007 # To store the factorials # of all numbers factorial = [0 for i in range(100005)] # Function to calculate factorial # of all numbers def StoreFactorials(n): factorial[0] = 1 for i in range(1, n + 1, 1): factorial[i] = (i * factorial[i - 1]) % mod # Calculate x to the power y # in O(log n) time def Power(x, y): ans = 1 while (y > 0): if (y % 2 == 1): ans = (ans * x) % mod x = (x * x) % mod y //= 2 return ans # Function to find inverse mod # of a number x def invmod(x): return Power(x, mod - 2) # Calculate (n C r) def nCr(n, r): return ((factorial[n] * invmod((factorial[r] * factorial[n - r]) % mod)) % mod) def CountWays(n, k): StoreFactorials(n) # Loop to compute the formula # evaluated ans = 0 i = k while(i >= 0): if (i % 2 == k % 2): # Add even power terms ans = ((ans + (Power(i, n) * nCr(k, i)) % mod) % mod) else: # Subtract odd power terms ans = ((ans + mod - (Power(i, n) * nCr(k, i)) % mod) % mod) i -= 1 # Choose the k boxes which # were used ans = (ans * nCr(n, k)) % mod return ans # Driver code if __name__ == '__main__': N = 5 K = 5 print(CountWays(N, K)) # This code is contributed by Surendra_Gangwar
C#
// C# program to calculate the
// above formula
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
static long mod = 1000000007;
// To store the factorials
// of all numbers
static long []factorial = new long[100005];
// Function to calculate factorial
// of all numbers
static void StoreFactorials(int n)
{
factorial[0] = 1;
for(int i = 1; i <= n; i++)
{
factorial[i] = (i *
factorial[i - 1]) % mod;
}
}
// Calculate x to the power y
// in O(log n) time
static long Power(long x, long y)
{
long ans = 1;
while (y > 0)
{
if (y % 2 == 1)
{
ans = (ans * x) % mod;
}
x = (x * x) % mod;
y /= 2;
}
return ans;
}
// Function to find inverse mod of
// a number x
static long invmod(long x)
{
return Power(x, mod - 2);
}
// Calculate (n C r)
static long nCr(int n, int r)
{
return (factorial[n] *
invmod((factorial[r] *
factorial[n - r]) % mod)) % mod;
}
static long CountWays(int n,int k)
{
StoreFactorials(n);
// Loop to compute the formula
// evaluated
long ans = 0;
for(int i = k; i >= 0; i--)
{
if (i % 2 == k % 2)
{
// Add even power terms
ans = (ans + (Power(i, n) *
nCr(k, i)) % mod) % mod;
}
else
{
// Subtract odd power terms
ans = (ans + mod - (Power(i, n) *
nCr(k, i)) % mod) % mod;
}
}
// Choose the k boxes which
// were used
ans = (ans * nCr(n, k)) % mod;
return ans;
}
// Driver Code
public static void Main (string[] args)
{
int N = 5;
int K = 5;
Console.Write(CountWays(N, K) + "\n");
}
}
// This code is contributed by rutvik_56
Producción:
120
Complejidad del tiempo: O(N*log N)
Espacio Auxiliar: O(10 5 )
Publicación traducida automáticamente
Artículo escrito por Shrey Tanna y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA