Encuentre formas de organizar K bolas verdes entre N bolas de manera que se necesiten exactamente i movimientos para recolectar todas las K bolas verdes.

Dados dos enteros N y K . Hay N bolas colocadas en fila. K de ellos son verdes y N – K de ellos son negros. La tarea es encontrar el número de formas de organizar N bolas de modo que se necesiten exactamente i ( 1 ≤ i ≤ K ) movimientos para recoger todas las bolas verdes. En un solo movimiento, podemos recoger cualquier grupo de bolas verdes consecutivas. Tenga en cuenta que la respuesta puede ser muy grande. Entonces, salida respuesta módulo 10 ⁹ + 7 .

Ejemplos: 

Entrada: N = 5, K = 3 
Salida: 3 6 1 
Hay tres formas de colocar las bolas para que 
se necesite exactamente un movimiento: 
(G, G, G, B, B), (B, G, G, G, B) y (B, B, G, G, G).
Hay seis formas de colocar las bolas para que 
se necesiten exactamente dos movimientos: 
(G, G, B, G, B), (G, G, B, B, G), (B, G, G, B, G), (B, G, B, G, G), 
(G, B, G, G, B) y (G, B, B, G, G).
Solo hay una forma de colocar las bolas de modo que 
se necesiten exactamente tres movimientos: (G, B, G, B, G).

Entrada: N = 100, K = 5 
Salida: 96 18240 857280 13287840 61124064 
 

Enfoque: Solo se deben realizar i movimientos para recolectar K bolas verdes, lo que significa que las K bolas verdes están separadas en i lugares por bolas negras. Por lo tanto, consideremos la combinación de la siguiente manera. 

• Primero, coloque las bolas negras N – K en una fila.
• Entre estas bolas negras, seleccione i lugares desde el extremo izquierdo hasta el extremo derecho y considere colocar K bolas verdes allí. Hay ^{N – K + 1} C _i formas de elegirlas.
• Para cada opción, considere cuántas bolas verdes se asignarán a cada espacio. Dado que es necesario asignar uno o más a cada uno, hay ^{K – 1} C _{i – 1} formas de determinar esto.

Por lo tanto, para cada i , la respuesta es ^{N – K + 1} C _i * ^{K – 1} C _{i – 1} . Encontrar ⁿ C _r se discute aquí .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define mod (int)(1e9 + 7)
 
// To store the factorial and the
// factorial mod inverse of a number
int factorial[N], modinverse[N];
 
// Function to find (a ^ m1) % mod
int power(int a, int m1)
{
    if (m1 == 0)
        return 1;
    else if (m1 == 1)
        return a;
    else if (m1 == 2)
        return (1LL * a * a) % mod;
    else if (m1 & 1)
        return (1LL * a
                * power(power(a, m1 / 2), 2))
               % mod;
    else
        return power(power(a, m1 / 2), 2) % mod;
}
 
// Function to find factorial
// of all the numbers
void factorialfun()
{
    factorial[0] = 1;
    for (int i = 1; i < N; i++)
        factorial[i] = (1LL
                        * factorial[i - 1] * i)
                       % mod;
}
 
// Function to find the factorial
// mod inverse of all the numbers
void modinversefun()
{
    modinverse[N - 1]
        = power(factorial[N - 1], mod - 2) % mod;
 
    for (int i = N - 2; i >= 0; i--)
        modinverse[i] = (1LL * modinverse[i + 1]
                         * (i + 1))
                        % mod;
}
 
// Function to return nCr
int binomial(int n, int r)
{
    if (r > n)
        return 0;
 
    int a = (1LL * factorial[n]
             * modinverse[n - r])
            % mod;
 
    a = (1LL * a * modinverse[r]) % mod;
    return a;
}
 
// Function to find ways to arrange K green
// balls among N balls such that we need
// exactly i moves to collect all K green balls
void arrange_balls(int n, int k)
{
    factorialfun();
    modinversefun();
 
    for (int i = 1; i <= k; i++)
        cout << (1LL * binomial(n - k + 1, i)
                 * binomial(k - 1, i - 1))
                    % mod
             << " ";
}
 
// Driver code
int main()
{
    int n = 5, k = 3;
 
    // Function call
    arrange_balls(n, k);
 
    return 0;
}

# Python3 implementation of the approach
N = 100005
mod = (int)(1e9 + 7)
 
# To store the factorial and the
# factorial mod inverse of a number
factorial = [0] * N;
modinverse = [0] * N;
 
# Function to find (a ^ m1) % mod
def power(a, m1) :
     
    if (m1 == 0) :
        return 1;
    elif (m1 == 1) :
        return a;
    elif (m1 == 2) :
        return (a * a) % mod;
    elif (m1 & 1) :
        return (a * power(power(a, m1// 2), 2)) % mod;
    else :
        return power(power(a, m1 // 2), 2) % mod;
 
# Function to find factorial
# of all the numbers
def factorialfun() :
 
    factorial[0] = 1;
    for i in range(1, N) :
        factorial[i] = (factorial[i - 1] * i) % mod;
 
# Function to find the factorial
# mod inverse of all the numbers
def modinversefun() :
    modinverse[N - 1] = power(factorial[N - 1],
                                mod - 2) % mod;
     
    for i in range(N - 2 , -1, -1) :
        modinverse[i] = (modinverse[i + 1] *
                                   (i + 1)) % mod;
 
# Function to return nCr
def binomial(n, r) :
 
    if (r > n) :
        return 0;
 
    a = (factorial[n] *
         modinverse[n - r]) % mod;
 
    a = (a * modinverse[r]) % mod;
    return a;
 
# Function to find ways to arrange K green
# balls among N balls such that we need
# exactly i moves to collect all K green balls
def arrange_balls(n, k) :
    factorialfun();
    modinversefun();
 
    for i in range(1, k + 1) :
        print((binomial(n - k + 1, i) *
               binomial(k - 1, i - 1)) % mod,
                                  end = " ");
 
# Driver code
if __name__ == "__main__" :
 
    n = 5; k = 3;
 
    # Function call
    arrange_balls(n, k);
 
# This code is contributed by AnkitRai01

// Java implementation of the approach
 
import java.util.*;
 
class GFG{
static final int N = 100005;
static final int mod = (int)(1e9 + 7);
 
// To store the factorial and the
// factorial mod inverse of a number
static long []factorial = new long[N];
static long []modinverse = new long[N];
 
 
// Function to find (a ^ m1) % mod
static long power(long a, int m1)
{
    if (m1 == 0)
        return 1;
    else if (m1 == 1)
        return a;
    else if (m1 == 2)
        return (1L * a * a) % mod;
    else if (m1 %2== 1)
        return (1L * a
                * power(power(a, m1 / 2), 2))
               % mod;
    else
        return power(power(a, m1 / 2), 2) % mod;
}
 
// Function to find factorial
// of all the numbers
static void factorialfun()
{
    factorial[0] = 1;
    for (int i = 1; i < N; i++)
        factorial[i] = (1L
                        * factorial[i - 1] * i)
                       % mod;
}
 
// Function to find the factorial
// mod inverse of all the numbers
static void modinversefun()
{
    modinverse[N - 1]
        = (int) (power(factorial[N - 1], mod - 2) % mod);
 
    for (int i = N - 2; i >= 0; i--)
        modinverse[i] = (1 * modinverse[i + 1]
                         * (i + 1))
                        % mod;
}
 
// Function to return nCr
static long binomial(int n, int r)
{
    if (r > n)
        return 0;
 
    long a = (1L * factorial[n]
             * modinverse[n - r])
            % mod;
 
    a = (1 * a * modinverse[r]) % mod;
    return a;
}
 
// Function to find ways to arrange K green
// balls among N balls such that we need
// exactly i moves to collect all K green balls
static void arrange_balls(int n, int k)
{
    factorialfun();
    modinversefun();
 
    for (int i = 1; i <= k; i++)
        System.out.print((1L * binomial(n - k + 1, i)
                 * binomial(k - 1, i - 1))
                    % mod
            + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5, k = 3;
 
    // Function call
    arrange_balls(n, k);
 
}
}
 
// This code contributed by Princi Singh

// C# implementation of the approach
using System;
 
class GFG{
     
static readonly int N = 100005;
static readonly int mod = (int)(1e9 + 7);
 
// To store the factorial and the
// factorial mod inverse of a number
static long []factorial = new long[N];
static long []modinverse = new long[N];
 
// Function to find (a ^ m1) % mod
static long power(long a, int m1)
{
    if (m1 == 0)
        return 1;
    else if (m1 == 1)
        return a;
    else if (m1 == 2)
        return (1L * a * a) % mod;
    else if (m1 % 2 == 1)
        return (1L * a *
        power(power(a, m1 / 2), 2)) % mod;
    else
        return power(power(a, m1 / 2), 2) % mod;
}
 
// Function to find factorial
// of all the numbers
static void factorialfun()
{
    factorial[0] = 1;
    for(int i = 1; i < N; i++)
        factorial[i] = (1L * factorial[i - 1] * i) % mod;
}
 
// Function to find the factorial
// mod inverse of all the numbers
static void modinversefun()
{
    modinverse[N - 1] = (int)(power(factorial[N - 1],
                                            mod - 2) % mod);
    for(int i = N - 2; i >= 0; i--)
        modinverse[i] = (1 * modinverse[i + 1] *
                        (i + 1)) % mod;
}
 
// Function to return nCr
static long binomial(int n, int r)
{
    if (r > n)
        return 0;
 
    long a = (1L * factorial[n] *
    modinverse[n - r]) % mod;
 
    a = (1 * a * modinverse[r]) % mod;
    return a;
}
 
// Function to find ways to arrange K green
// balls among N balls such that we need
// exactly i moves to collect all K green balls
static void arrange_balls(int n, int k)
{
    factorialfun();
    modinversefun();
 
    for(int i = 1; i <= k; i++)
        Console.Write((1L * binomial(n - k + 1, i) *
                            binomial(k - 1, i - 1)) %
                                   mod + " ");
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 5, k = 3;
 
    // Function call
    arrange_balls(n, k);
}
}
 
// This code is contributed by 29AjayKumar

3 6 1