Contar formas de colocar M objetos en distintas particiones de N cajas

Posted on by Rudeus Greyrat

Dados dos enteros positivos N y M , la tarea es encontrar el número de formas de colocar M objetos distintos en particiones de cajas indexadas pares que están numeradas [1, N] secuencialmente, y cada caja i -ésima tiene i particiones distintas. Dado que la respuesta puede ser muy grande, imprima módulo 1000000007 .

Ejemplos:

Entrada: N = 2, M = 1
Salida: 2
Explicación: Dado que, N = 2. Solo hay una caja indexada par, es decir, la caja 2, que tiene 2 particiones. Por lo tanto, hay dos posiciones para colocar un objeto. Por lo tanto, número de vías = 2.

Entrada: N = 5, M = 2
Salida: 32

 

Enfoque: siga los pasos a continuación para resolver el problema:

  • Los objetos M deben colocarse en particiones de cajas indexadas pares. Sea S el total de particiones de cajas indexadas pares en N cajas.
  • El número de particiones es igual a la suma de todos los números pares hasta N. Por lo tanto, Sum, S = X * (X + 1), donde X = piso (N / 2).
  • Cada objeto puede ocupar una de S posiciones diferentes. Por lo tanto, el número total de vías = S*S*S..(M veces) = S M .

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

C++

// C++ implementation of the
// above Approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
int power(int x, unsigned int y, int p = MOD)
{
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * 1LL * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * 1LL * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
void totalWays(int N, int M)
{
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * 1LL * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    cout << power(S, M, MOD) << "\n";
}
 
// Driver Code
int main()
{
    // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
 
    return 0;
}

Java

// Java implementation of the
// above Approach
import java.io.*;
class GFG
{
   
public static int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{   
      p = MOD;
   
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0)
    {
 
        // If y is odd, multiply x with result
        if ((y & 1) != 0)
            res = (res * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
static void totalWays(int N, int M)
{
   
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    System.out.println(power(S, M, MOD));
}
 
// Driver Code
public static void main (String[] args)
{
     
      // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
}
}
 
// This code is contributed by Dharanendra L V

Python3

# Python3 implementation of the
# above Approach
MOD = 1000000007
 
# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p = MOD):
   
    # Initialize Result
    res = 1
 
    # Update x if x >= MOD
    # to avoid multiplication overflow
    x = x % p
    while (y > 0):
 
        # If y is odd, multiply x with result
        if (y & 1):
            res = (res * x) % p
 
        # multiplied by long long int,
        # to avoid overflow
        # because res * x <= 1e18, which is
        # out of bounds for integer
 
        # n must be even now
 
        # y = y/2
        y = y >> 1
 
        # Change x to x^2
        x = (x * x) % p
    return res
 
# Utility function to find
# the Total Number of Ways
def totalWays(N, M):
   
    # Number of Even Indexed
    # Boxes
    X = N // 2
 
    # Number of partitions of
    # Even Indexed Boxes
    S = (X * (X + 1)) % MOD
 
    # Number of ways to distribute
    # objects
    print (power(S, M, MOD))
 
# Driver Code
if __name__ == '__main__':
 
    # N = number of boxes
    # M = number of distinct objects
    N, M = 5, 2
 
    # Function call to
    # get Total Number of Ways
    totalWays(N, M)
 
# This code is contributed by mohit kumar 29.

C#

// C# implementation of the
// above Approach
 
using System;
 
public class GFG{
 
public static int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
       
      p = MOD;
   
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if ((y & 1) != 0)
            res = (res * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
static void totalWays(int N, int M)
{
   
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    Console.WriteLine(power(S, M, MOD));
}
 
// Driver Code
static public void Main ()
{
 
    // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
}
}
 
// This code is contributed by Dharanendra L V

Javascript

<script>
 
// Javascript implementation of the
// above Approach
 
var MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
function power(x, y, p = MOD)
{
    // Initialize Result
    var res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * 1 * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * 1 * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
function totalWays(N, M)
{
    // Number of Even Indexed
    // Boxes
    var X = parseInt(N / 2);
 
    // Number of partitions of
    // Even Indexed Boxes
    var S = (X * 1 * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    document.write( power(S, M, MOD) << "<br>");
}
 
// Driver Code
// N = number of boxes
// M = number of distinct objects
var N = 5, M = 2;
// Function call to
// get Total Number of Ways
totalWays(N, M);
 
</script>
Producción: 

36

 

Complejidad temporal: O(log M)
Espacio auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *