Рубрики

Посчитай способ разделить круг, используя N непересекающихся аккордов | Set-2

Дано число N. Задача состоит в том, чтобы найти количество способов нарисовать N аккордов по кругу с 2 * N точками, чтобы не пересекались никакие два аккорда. Два пути различны, если существует аккорд, который присутствует в одном, а не в другом. Ответ может быть крупным шрифтом по модулю 10 ^ 9 + 7.

Примеры:

Input : N = 2
Output : 2
If points are numbered 1 to 4 in clockwise direction,
then different ways to draw chords are:
{(1-2), (3-4)} and {(1-4), (2-3)}

Input :N = 1
Output : 1

Подходить:
Если мы проведем аккорд между любыми двумя точками, текущий набор точек будет разбит на два меньших набора S_1 и S_2. Если мы рисуем аккорд из точки в S_1 в точку в S_2, он наверняка пересечет аккорд, который мы только что нарисовали. Итак, мы можем прийти к повторению, что:

Ways(n) = sum[i = 0 to n-1] { Ways(i)*Ways(n-i-1) }.

Вышеупомянутое рекуррентное отношение аналогично рекуррентному отношению для n- го каталонского числа, которое равно 2n C n / (n + 1) . Вместо деления нумерации на деноминацию, умножьте нумератор на обратное по модулю знаменателя, так как деление не допускается в области по модулю.

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

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для эффективного расчета x ^ y% mod

int power(long long x, int y, int mod)

{

  

    // Инициализируем ответ

    long long res = 1;

    while (y) {

  

        // Если сила нечетная

        if (y & 1)

  

            // Обновить ответ

            res = (res * x) % mod;

  

        // Квадрат основания и половины экспоненты

        x = (x * x) % mod;

        y = (y >> 1);

    }

  

    // Возвращаем значение

    return (int)(res % mod);

}

  

  

  
// Функция для эффективного расчета ncr% mod

int ncr(int n, int r, int mod)

{

  

    // Инициализируем ответ

    long long res = 1;

  

    // Рассчитаем ncr в O (r)

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

  

        // Умножаем на коэффициент числителя

        res = (res * (n - i + 1)) % mod;

  

        // Рассчитать обратный коэффициент знаменателя

        int inv = power(i, mod - 2, mod);

  

        // Умножаем с обратным значением

        res = (res * inv) % mod;

    }

  

    // Возвращаем значение ответа

    return (int)(res%mod);

}

  
// Функция для возврата числа
// непересекающихся аккордов

int NoOfChords(int A)

{

  

    // определить значение мода

    int mod = 1e9 + 7;

  

    // Значение C (2n, n)

    long long ans = ncr(2 * A, A, mod);

  

    // по модулю обратной (n + 1)

    int inv = power(A + 1, mod - 2, mod);

  

    // Умножаем с обратным по модулю

    ans = (ans * inv) % mod;

  

    // Вернуть ответ

    return (int)(ans%mod);

}

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

int main()

{

  

    int N = 2;

      

    // вызов функции

    cout << NoOfChords(N);

  

    return 0;

}

Джава

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

class GFG

{

  

    // Функция для эффективного расчета x ^ y% mod

    static int power(long x, int y, int mod) 

    

      

        // Инициализируем ответ

        long res = 1

        while (y != 0)

        

      

            // Если сила нечетная

            if ((y & 1) == 1

      

                // Обновить ответ

                res = (res * x) % mod; 

      

            // Квадрат основания и половины экспоненты

            x = (x * x) % mod; 

            y = (y >> 1); 

        

      

        // Возвращаем значение

        return (int)(res % mod); 

    

      

    // Функция для эффективного расчета ncr% mod

    static int ncr(int n, int r, int mod) 

    

      

        // Инициализируем ответ

        long res = 1

      

        // Рассчитаем ncr в O (r)

        for (int i = 1; i <= r; i += 1

        

      

            // Умножаем на коэффициент числителя

            res = (res * (n - i + 1)) % mod; 

      

            // Рассчитать обратное

            // фактор знаменателя

            int inv = power(i, mod - 2, mod); 

      

            // Умножаем с обратным значением

            res = (res * inv) % mod; 

        

      

        // Возвращаем значение ответа

        return (int)(res % mod); 

    

      

    // Функция для возврата числа

    // непересекающихся аккордов

    static int NoOfChords(int A) 

    

      

        // определить значение мода

        int mod = (int)(1e9 + 7); 

      

        // Значение C (2n, n)

        long ans = ncr(2 * A, A, mod); 

      

        // по модулю обратной (n + 1)

        int inv = power(A + 1, mod - 2, mod); 

      

        // Умножаем с обратным по модулю

        ans = (ans * inv) % mod; 

      

        // Вернуть ответ

        return (int)(ans % mod); 

    

      

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

    public static void main(String[] args) 

    {

        int N = 2

      

        // вызов функции

        System.out.println(NoOfChords(N));

    }

}

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

python3

# Python3 реализация вышеуказанного подхода

  
# Функция для эффективного расчета x ^ y% mod

def power(x, y, mod):

  

    # Инициализировать ответ

    res = 1

    while (y):

  

        # Если сила нечетная

        if (y & 1):

  

            # Обновить ответ

            res = (res * x) % mod

  

        # Квадрат базы и половина экспоненты

        x = (x * x) % mod

        y = (y >> 1)

  

  

    # Вернуть значение

    return (res % mod)

  
# Функция для эффективного расчета ncr% mod

def ncr(n, r, mod):

  

  

    # Инициализировать ответ

    res = 1

  

    # Рассчитать ncr в O (r)

    for i in range(1,r+1):

  

        # Умножить на коэффициент числителя

        res = (res * (n - i + 1)) % mod

  

        # Рассчитать обратный коэффициент знаменателя

        inv = power(i, mod - 2, mod)

  

        # Умножить с обратным значением

        res = (res * inv) % mod

  

  

    # Возвращаем значение ответа

    return (res%mod)

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

def NoOfChords(A):

  

  

    # определить значение мода

    mod = 10**9 + 7

  

    # Значение C (2n, n)

    ans = ncr(2 * A, A, mod)

  

    # По модулю обратное (n + 1)

    inv = power(A + 1, mod - 2, mod)

  

    # Умножить с обратным по модулю

    ans = (ans * inv) % mod

  

    # Вернуть ответ

    return (ans%mod)

  

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

  

N = 2

  
# Вызов функции

print(NoOfChords(N))

  
# Этот код предоставлен mohit kumar 29

C #

// Java реализация вышеуказанного подхода

using System;

  

class GFG 

{

  

    // Функция для эффективного расчета x ^ y% mod

    static int power(long x, int y, int mod) 

    

      

        // Инициализируем ответ

        long res = 1; 

        while (y != 0)

        

      

            // Если сила нечетная

            if ((y & 1) == 1) 

      

                // Обновить ответ

                res = (res * x) % mod; 

      

            // Квадрат основания и половины экспоненты

            x = (x * x) % mod; 

            y = (y >> 1); 

        

      

        // Возвращаем значение

        return (int)(res % mod); 

    

      

    // Функция для эффективного расчета ncr% mod

    static int ncr(int n, int r, int mod) 

    

      

        // Инициализируем ответ

        long res = 1; 

      

        // Рассчитаем ncr в O (r)

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

        

      

            // Умножаем на коэффициент числителя

            res = (res * (n - i + 1)) % mod; 

      

            // Рассчитать обратный коэффициент знаменателя

            int inv = power(i, mod - 2, mod); 

      

            // Умножаем с обратным значением

            res = (res * inv) % mod; 

        

      

        // Возвращаем значение ответа

        return (int)(res % mod); 

    

      

    // Функция для возврата числа

    // непересекающихся аккордов

    static int NoOfChords(int A) 

    

      

        // определить значение мода

        int mod = (int)(1e9 + 7); 

      

        // Значение C (2n, n)

        long ans = ncr(2 * A, A, mod); 

      

        // по модулю обратной (n + 1)

        int inv = power(A + 1, mod - 2, mod); 

      

        // Умножаем с обратным по модулю

        ans = (ans * inv) % mod; 

      

        // Вернуть ответ

        return (int)(ans % mod); 

    

      

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

    public static void Main () 

    {

        int N = 2; 

          

        // вызов функции

        Console.WriteLine(NoOfChords(N));

    }

}

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

Выход:

2

Временная сложность: O (N * log (mod))

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

Посчитай способ разделить круг, используя N непересекающихся аккордов | Set-2

0.00 (0%) 0 votes