Рубрики

Приложение к теореме Бертрана о голосовании

Учитывая количество 'X' и 'Y' в строке, которая состоит из символов из набора {'X', 'Y'} , задача состоит в том, чтобы найти количество перестановок, которые удовлетворяют условию, когда каждая подстрока перестановка, начинающаяся с первого символа, имеет число ('X')> количество ('Y') . Выведите ответ по модулю 1000000007. Обратите внимание, что число «X» всегда будет больше, чем число «Y» в данной строке.

Примеры:

Input: X = 2, Y = 1
Output: 1
The possible distributions are “XYX”, “XXY” and “YXX”
Distribution 1: Till 1st index (X = 1, Y = 0), till 2nd index (X = 1, Y = 1) and till 3rd index (X = 2, Y = 1). Number of X isn’t always greater than Y so this distribution is not valid.
Distribution 2: 1st index (X = 1, Y = 0), 2nd index (X = 2, Y = 0) and 3rd index (X = 2, Y = 1). This is a valid distribution as X is always greater than Y.
Distribution 3: 1st index (X = 0, Y = 1), 2nd index (X = 1, Y = 1) and 3rd index (X = 2, Y = 1). Invalid distribution.

Input: X = 3, Y = 1
Output: 1

Подход: проблема такого типа может быть решена с помощью теоремы Бертрана о голосовании . Из всех возможных распределений вероятность того, что X всегда остается в лидере, равна (X — Y) / (X + Y) . И общее количество раздач (X + Y)! / (X! * Y!) . Следовательно, распределения, в которых X всегда имеет преимущество, (X + Y — 1)! * (X — Y) / (X! * Y!) .
Для расчета (X + Y — 1)! * (X — Y) / (X! * Y!) , Нам нужно вычислить мультипликативную модульную инверсию X! и, таким образом, аналогично для Y. Так как 1000000007 является простым, согласно Маленькой Теореме Ферма: (1 / X!)% 1000000007 = ((X!) (1000000007 — 2) )% 1000000007 . Аналогичный результат справедлив и для Y.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

#define ll long long

  
ll mod = 1000000007;
ll arr[1000001] = { 0 };

  
// Функция для вычисления факториала
// номера мод 1000000007

void cal_factorial()

{

    arr[0] = 1;

  

    // Факториал i = факториал (i - 1) * i;

    for (int i = 1; i <= 1000000; i++) {

  

        // Взятие мода вместе с расчетом.

        arr[i] = (arr[i - 1] * i) % mod;

    }

}

  
// Функция для модульного возведения в степень
ll mod_exponent(ll num, ll p)
{

  

    if (p == 0)

        return 1;

  

    // Если p нечетно

    if (p & 1) {

        return ((num % mod)

                * (mod_exponent((num * num) % mod, p / 2))

                % mod)

               % mod;

    }

  

    // Если p четное

    else if (!(p & 1))

        return (mod_exponent((num * num) % mod, p / 2))

               % mod;

}

  
// Функция для возврата количества
// требуемые перестановки
ll getCount(ll x, ll y)
{

    ll ans = arr[x + y - 1];

  

    // Расчет мультипликативного модульного обратного

    // для х! и умножение с ANS

    ans *= mod_exponent(arr[x], mod - 2);

    ans %= mod;

  

    // Расчет мультипликативного модульного обратного

    // для тебя! и умножение с ANS

    ans *= mod_exponent(arr[y], mod - 2);

    ans %= mod;

  

    ans *= (x - y);

    ans %= mod;

    return ans;

}

  
// Код драйвера

int main()

{

  

    // Предварительно вычислить факториалы

    cal_factorial();

  

    ll x = 3, y = 1;

    cout << getCount(x, y);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

      

static long mod = 1000000007;

static long[] arr = new long[1000001];

  
// Функция для вычисления факториала
// номера мод 1000000007

static void cal_factorial()

{

    arr[0] = 1;

  

    // Факториал i = факториал (i - 1) * i;

    for (int i = 1; i <= 1000000; i++) 

    {

  

        // Взятие мода вместе с расчетом.

        arr[i] = ((arr[i - 1] * i) % mod);

    }

}

  
// Функция для модульного возведения в степень

static long mod_exponent(long num, long p)

{

  

    if (p == 0)

        return 1;

  

    // Если p нечетно

    if ((p & 1) != 0

    {

        return ((num % mod)

                * (mod_exponent((num * num) % mod, p / 2))

                % mod)

            % mod;

    }

  

    // Если p четное

    else

        return (mod_exponent((num * num) % mod, p / 2))

            % mod;

}

  
// Функция для возврата количества
// требуемые перестановки

static long getCount(long x, long y)

{

    long ans = arr[(int)x + (int)y - 1];

  

    // Расчет мультипликативного модульного обратного

    // для х! и умножение с ANS

    ans *= mod_exponent(arr[(int)x], mod - 2);

    ans %= mod;

  

    // Расчет мультипликативного модульного обратного

    // для тебя! и умножение с ANS

    ans *= mod_exponent(arr[(int)y], mod - 2);

    ans %= mod;

  

    ans *= (x - y);

    ans %= mod;

    return ans;

}

  
// Код драйвера

public static void main (String[] args)

{

  

    // Предварительно вычислить факториалы

    cal_factorial();

  

    long x = 3, y = 1;

    System.out.println(getCount(x, y));

}
}

  
// Этот код предоставлен chandan_jnu

python3

# Python3 реализация подхода

mod = 1000000007

arr = [0] * (1000001

  
# Функция для расчета факториала
№ мод числа 1000000007

def cal_factorial():

  

    arr[0] = 1

  

    # Факториал я = факториал

    # из (i - 1) * i

    for i in range(1, 1000001): 

          

        # Принимая мод вместе с расчетом.

        arr[i] = (arr[i - 1] * i) % mod

      
# Функция для модульного возведения в степень

def mod_exponent(num, p):

  

    if (p == 0):

        return 1

  

    # Если p нечетно

    if (p & 1) :

        return ((num % mod)* (mod_exponent((num * num) % 

                              mod, p // 2)) % mod) % mod

      

    # Если р четное

    elif (not(p & 1)):

        return (mod_exponent((num * num) % 

                              mod, p // 2))% mod

  
# Функция для возврата отсчета
# необходимые перестановки

def getCount(x, y):

  

    ans = arr[x + y - 1]

  

    # Расчет мультипликативного модульного обратного

    # для х! и умножение с ANS

    ans *= mod_exponent(arr[x], mod - 2)

    ans %= mod

  

    # Расчет мультипликативного модульного обратного

    # для тебя! и умножение с ANS

    ans *= mod_exponent(arr[y], mod - 2)

    ans %= mod

  

    ans *= (x - y)

    ans %= mod

    return ans

      
Код водителя

if __name__ == '__main__':

      

    # Предварительно вычислить факториалы

    cal_factorial()

  

    x = 3

    y = 1

    print(getCount(x, y))

  
# Этот код предоставлен
# SHUBHAMSINGH10

C #

// C # реализация подхода

class GFG

{

static long mod = 1000000007;

static long[] arr=new long[1000001];

  
// Функция для вычисления факториала
// номера мод 1000000007

static void cal_factorial()

{

    arr[0] = 1;

  

    // Факториал i = факториал (i - 1) * i;

    for (long i = 1; i <= 1000000; i++) 

    {

  

        // Взятие мода вместе с расчетом.

        arr[i] = (arr[i - 1] * i) % mod;

    }

}

  
// Функция для модульного возведения в степень

static long mod_exponent(long num, long p)

{

  

    if (p == 0)

        return 1;

  

    // Если p нечетно

    if ((p & 1)!=0) 

    {

        return ((num % mod)

                * (mod_exponent((num * num) % mod, p / 2))

                % mod)

            % mod;

    }

  

    // Если p четное

    else

        return (mod_exponent((num * num) % mod, p / 2))

            % mod;

}

  
// Функция для возврата количества
// требуемые перестановки

static long getCount(long x, long y)

{

    long ans = arr[x + y - 1];

  

    // Расчет мультипликативного модульного обратного

    // для х! и умножение с ANS

    ans *= mod_exponent(arr[x], mod - 2);

    ans %= mod;

  

    // Расчет мультипликативного модульного обратного

    // для тебя! и умножение с ANS

    ans *= mod_exponent(arr[y], mod - 2);

    ans %= mod;

  

    ans *= (x - y);

    ans %= mod;

    return ans;

}

  
// Код драйвера

static void Main()

{

  

    // Предварительно вычислить факториалы

    cal_factorial();

  

    long x = 3, y = 1;

    System.Console.WriteLine(getCount(x, y));

}
}

  
// Этот код предоставлен chandan_jnu

PHP

<?php
// PHP реализация подхода

$mod = 1000000007;

$arr = array_fill(0, 10001, 0);

  
// Функция для вычисления факториала
// номера мод 1000000007

function cal_factorial()

{

    global $arr, $mod;

    $arr[0] = 1;

  

    // Факториал я = факториал

    // of (i - 1) * i;

    for ($i = 1; $i <= 10000; $i++) 

    {

  

        // Получение мод с расчетом.

        $arr[$i] = ($arr[$i - 1] * $i) % $mod;

    }

}

  
// Функция для модульного возведения в степень

function mod_exponent($num, $p)

{

    global $mod;

    if ($p == 0)

        return 1;

  

    // Если p нечетно

    if (($p & 1))

    {

        return (($num % $mod)* (mod_exponent(($num * $num) % 

                            $mod, $p / 2)) % $mod) % $mod;

    }

  

    // Если p четное

    else if (!($p & 1))

        return (mod_exponent(($num * $num) % 

                              $mod, $p / 2))% $mod;

}

  
// Функция для возврата количества
// требуемые перестановки

function getCount($x, $y)

{

    global $arr, $mod;

    $ans = $arr[$x + $y - 1];

  

    // Расчет мультипликативного модульного

    // обратный для х! и умножение с ANS

    $ans *= mod_exponent($arr[$x], $mod - 2);

    $ans %= $mod;

  

    // Расчет мультипликативного модульного

    // обратный для y! и умножение с ANS

    $ans *= mod_exponent($arr[$y], $mod - 2);

    $ans %= $mod;

  

    $ans *= ($x - $y);

    $ans %= $mod;

    return $ans;

}

  
// Код драйвера

  
// Предварительно вычислить факториалы
cal_factorial();

  

$x = 3;

$y = 1;

print(getCount($x, $y));

  
// Этот код предоставлен chandan_jnu
?>

Выход:

2

Рекомендуемые посты:

Приложение к теореме Бертрана о голосовании

0.00 (0%) 0 votes