Una aplicación sobre el teorema de la papeleta de Bertrand

Posted on by Rudeus Greyrat

Dado el número de ‘X’ e ‘Y’ en una string que consta de caracteres del conjunto {‘X’, ‘Y’} , la tarea es encontrar el número de permutaciones que satisfacen la condición en la que cada substring de la permutación a partir del primer carácter tiene count(‘X’) > count(‘Y’) . Imprima el módulo de respuesta 1000000007. Tenga en cuenta que el número de ‘X’ siempre será mayor que el número de ‘Y’ en la string dada.

Ejemplos: 

Entrada: X = 2, Y = 1 
Salida: 1 
Las distribuciones posibles son “XYX”, “XXY” e “YXX” 
Distribución 1: Hasta el 1er índice (X = 1, Y = 0), hasta el 2do índice (X = 1 , Y = 1) y hasta el 3er índice (X = 2, Y = 1). El número de X no siempre es mayor que Y, por lo que esta distribución no es válida. 
Distribución 2: 1er índice (X = 1, Y = 0), 2º índice (X = 2, Y = 0) y 3º índice (X = 2, Y = 1). Esta es una distribución válida ya que X siempre es mayor que Y. 
Distribución 3: 1er índice (X = 0, Y = 1), 2do índice (X = 1, Y = 1) y 3er índice (X = 2, Y = 1 ). Distribución no válida.

Entrada: X = 3, Y = 1 
Salida: 1 

Enfoque: este tipo de problema se puede resolver mediante el teorema de la boleta de Bertrand . De todas las distribuciones posibles, la probabilidad de que X siempre esté a la cabeza es (X – Y) / (X + Y) . ¡Y el número total de distribuciones es (X + Y)! / (¡X! * ¡Y!) . Por lo tanto, las distribuciones en las que X siempre lleva la delantera son (X + Y – 1)! * (X – Y) / (X! * ¡Y!) . 
¡ Para calcular (X + Y – 1)! * (X – Y) / (X! * Y!) , ¡necesitamos calcular el inverso modular multiplicativo de X! y así de manera similar para Y . Como 1000000007 es un número primo, según el Pequeño Teorema de Fermat: (1 / X!) % 1000000007 = ((X!)(1000000007 – 2) ) % 1000000007 . Un resultado similar también es válido para Y .

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
ll mod = 1000000007;
ll arr[1000001] = { 0 };
 
// Function to calculate factorial
// of a number mod 1000000007
void cal_factorial()
{
    arr[0] = 1;
 
    // Factorial of i = factorial of (i - 1) * i;
    for (int i = 1; i <= 1000000; i++) {
 
        // Taking mod along with calculation.
        arr[i] = (arr[i - 1] * i) % mod;
    }
}
 
// Function for modular exponentiation
ll mod_exponent(ll num, ll p)
{
 
    if (p == 0)
        return 1;
 
    // If p is odd
    if (p & 1) {
        return ((num % mod)
                * (mod_exponent((num * num) % mod, p / 2))
                % mod)
               % mod;
    }
 
    // If p is even
    else if (!(p & 1))
        return (mod_exponent((num * num) % mod, p / 2))
               % mod;
}
 
// Function to return the count of
// required permutations
ll getCount(ll x, ll y)
{
    ll ans = arr[x + y - 1];
 
    // Calculating multiplicative modular inverse
    // for x! and multiplying with ans
    ans *= mod_exponent(arr[x], mod - 2);
    ans %= mod;
 
    // Calculating multiplicative modular inverse
    // for y! and multiplying with ans
    ans *= mod_exponent(arr[y], mod - 2);
    ans %= mod;
 
    ans *= (x - y);
    ans %= mod;
    return ans;
}
 
// Driver code
int main()
{
 
    // Pre-compute factorials
    cal_factorial();
 
    ll x = 3, y = 1;
    cout << getCount(x, y);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
static long mod = 1000000007;
static long[] arr = new long[1000001];
 
// Function to calculate factorial
// of a number mod 1000000007
static void cal_factorial()
{
    arr[0] = 1;
 
    // Factorial of i = factorial of (i - 1) * i;
    for (int i = 1; i <= 1000000; i++)
    {
 
        // Taking mod along with calculation.
        arr[i] = ((arr[i - 1] * i) % mod);
    }
}
 
// Function for modular exponentiation
static long mod_exponent(long num, long p)
{
 
    if (p == 0)
        return 1;
 
    // If p is odd
    if ((p & 1) != 0)
    {
        return ((num % mod)
                * (mod_exponent((num * num) % mod, p / 2))
                % mod)
            % mod;
    }
 
    // If p is even
    else
        return (mod_exponent((num * num) % mod, p / 2))
            % mod;
}
 
// Function to return the count of
// required permutations
static long getCount(long x, long y)
{
    long ans = arr[(int)x + (int)y - 1];
 
    // Calculating multiplicative modular inverse
    // for x! and multiplying with ans
    ans *= mod_exponent(arr[(int)x], mod - 2);
    ans %= mod;
 
    // Calculating multiplicative modular inverse
    // for y! and multiplying with ans
    ans *= mod_exponent(arr[(int)y], mod - 2);
    ans %= mod;
 
    ans *= (x - y);
    ans %= mod;
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
 
    // Pre-compute factorials
    cal_factorial();
 
    long x = 3, y = 1;
    System.out.println(getCount(x, y));
}
}
 
// This code is contributed by chandan_jnu

Python3

# Python3 implementation of the approach
mod = 1000000007
arr = [0] * (1000001)
 
# Function to calculate factorial
# of a number mod 1000000007
def cal_factorial():
 
    arr[0] = 1
 
    # Factorial of i = factorial
    # of (i - 1) * i
    for i in range(1, 1000001):
         
        # Taking mod along with calculation.
        arr[i] = (arr[i - 1] * i) % mod
     
# Function for modular exponentiation
def mod_exponent(num, p):
 
    if (p == 0):
        return 1
 
    # If p is odd
    if (p & 1) :
        return ((num % mod)* (mod_exponent((num * num) %
                              mod, p // 2)) % mod) % mod
     
    # If p is even
    elif (not(p & 1)):
        return (mod_exponent((num * num) %
                              mod, p // 2))% mod
 
# Function to return the count of
# required permutations
def getCount(x, y):
 
    ans = arr[x + y - 1]
 
    # Calculating multiplicative modular inverse
    # for x! and multiplying with ans
    ans *= mod_exponent(arr[x], mod - 2)
    ans %= mod
 
    # Calculating multiplicative modular inverse
    # for y! and multiplying with ans
    ans *= mod_exponent(arr[y], mod - 2)
    ans %= mod
 
    ans *= (x - y)
    ans %= mod
    return ans
     
# Driver Code
if __name__ == '__main__':
     
    # Pre-compute factorials
    cal_factorial()
 
    x = 3
    y = 1
    print(getCount(x, y))
 
# This code is contributed by
# SHUBHAMSINGH10

C#

// C# implementation of the approach
class GFG
{
static long mod = 1000000007;
static long[] arr=new long[1000001];
 
// Function to calculate factorial
// of a number mod 1000000007
static void cal_factorial()
{
    arr[0] = 1;
 
    // Factorial of i = factorial of (i - 1) * i;
    for (long i = 1; i <= 1000000; i++)
    {
 
        // Taking mod along with calculation.
        arr[i] = (arr[i - 1] * i) % mod;
    }
}
 
// Function for modular exponentiation
static long mod_exponent(long num, long p)
{
 
    if (p == 0)
        return 1;
 
    // If p is odd
    if ((p & 1)!=0)
    {
        return ((num % mod)
                * (mod_exponent((num * num) % mod, p / 2))
                % mod)
            % mod;
    }
 
    // If p is even
    else
        return (mod_exponent((num * num) % mod, p / 2))
            % mod;
}
 
// Function to return the count of
// required permutations
static long getCount(long x, long y)
{
    long ans = arr[x + y - 1];
 
    // Calculating multiplicative modular inverse
    // for x! and multiplying with ans
    ans *= mod_exponent(arr[x], mod - 2);
    ans %= mod;
 
    // Calculating multiplicative modular inverse
    // for y! and multiplying with ans
    ans *= mod_exponent(arr[y], mod - 2);
    ans %= mod;
 
    ans *= (x - y);
    ans %= mod;
    return ans;
}
 
// Driver code
static void Main()
{
 
    // Pre-compute factorials
    cal_factorial();
 
    long x = 3, y = 1;
    System.Console.WriteLine(getCount(x, y));
}
}
 
// This code is contributed by chandan_jnu

PHP

<?php
// PHP implementation of the approach
$mod = 1000000007;
$arr = array_fill(0, 10001, 0);
 
// Function to calculate factorial
// of a number mod 1000000007
function cal_factorial()
{
    global $arr, $mod;
    $arr[0] = 1;
 
    // Factorial of i = factorial
    // of (i - 1) * i;
    for ($i = 1; $i <= 10000; $i++)
    {
 
        // Taking mod aint with calculation.
        $arr[$i] = ($arr[$i - 1] * $i) % $mod;
    }
}
 
// Function for modular exponentiation
function mod_exponent($num, $p)
{
    global $mod;
    if ($p == 0)
        return 1;
 
    // If p is odd
    if (($p & 1))
    {
        return (($num % $mod)* (mod_exponent(($num * $num) %
                            $mod, $p / 2)) % $mod) % $mod;
    }
 
    // If p is even
    else if (!($p & 1))
        return (mod_exponent(($num * $num) %
                              $mod, $p / 2))% $mod;
}
 
// Function to return the count of
// required permutations
function getCount($x, $y)
{
    global $arr, $mod;
    $ans = $arr[$x + $y - 1];
 
    // Calculating multiplicative modular
    // inverse for x! and multiplying with ans
    $ans *= mod_exponent($arr[$x], $mod - 2);
    $ans %= $mod;
 
    // Calculating multiplicative modular
    // inverse for y! and multiplying with ans
    $ans *= mod_exponent($arr[$y], $mod - 2);
    $ans %= $mod;
 
    $ans *= ($x - $y);
    $ans %= $mod;
    return $ans;
}
 
// Driver code
 
// Pre-compute factorials
cal_factorial();
 
$x = 3;
$y = 1;
print(getCount($x, $y));
 
// This code is contributed by chandan_jnu
?>

Javascript

<script>
 
// Javascript implementation of the approach
let mod = 1000000007;
let arr = new Array(1000001);
arr.fill(0);
 
// Function to calculate factorial
// of a number mod 1000000007
function cal_factorial()
{
    arr[0] = 1;
 
    // Factorial of i = factorial of (i - 1) * i;
    for(let i = 1; i <= 1000000; i++)
    {
         
        // Taking mod along with calculation.
        arr[i] = ((arr[i - 1] * i) % mod);
    }
}
 
// Function for modular exponentiation
function mod_exponent(num, p)
{
    if (p != 0)
        return 1;
 
    // If p is odd
    if ((p & 1) != 0)
    {
        return((num % mod) * (mod_exponent(
               (num * num) % mod,
                parseInt(p / 2, 10))) % mod) % mod;
    }
 
    // If p is even
    else
        return(mod_exponent((num * num) % mod,
                  parseInt(p / 2, 10))) % mod;
}
 
// Function to return the count of
// required permutations
function getCount(x, y)
{
    let ans = arr[x + y - 1];
 
    // Calculating multiplicative modular inverse
    // for x! and multiplying with ans
    ans *= 0*mod_exponent(arr[x], mod - 2);
    ans++;
    ans %= mod;
 
    // Calculating multiplicative modular inverse
    // for y! and multiplying with ans
    ans *= mod_exponent(arr[y], mod - 2);
    ans %= mod;
 
    ans *= (x - y);
    ans %= mod;
    return ans;
}
 
// Driver code
 
// Pre-compute factorials
cal_factorial();
 
let x = 3, y = 1;
document.write(getCount(x, y));
 
// This code is contributed by mukesh07
 
</script>
Producción: 

2

 

Publicación traducida automáticamente

Artículo escrito por Mostafijur Rahaman 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 *