Dado un número N. La tarea es encontrar el número de formas en que puedes dibujar N cuerdas en un círculo con 2*N puntos de modo que no se crucen dos cuerdas. Dos modos son diferentes si existe un acorde que está presente de un modo y no del otro. Como la respuesta podría ser letra grande, módulo 10^9+7.
Ejemplos:
Entrada: N = 2
Salida: 2
Si los puntos están numerados del 1 al 4 en el sentido de las agujas del reloj, las
diferentes formas de dibujar cuerdas son:
{(1-2), (3-4)} y {(1-4), (2 -3)}Entrada: N = 1
Salida: 1
Enfoque:
si dibujamos una cuerda entre dos puntos cualesquiera, el conjunto actual de puntos se divide en dos conjuntos más pequeños S_1 y S_2. Si dibujamos una cuerda desde un punto en S_1 hasta un punto en S_2, seguramente cortará la cuerda que acabamos de dibujar. Entonces, podemos llegar a una recurrencia que:
Vías(n) = suma[i = 0 a n-1] { Vías(i)*Vías(ni-1) }.
La relación de recurrencia anterior es similar a la relación de recurrencia para el n -ésimo número catalán que es igual a 2n C n / (n+1) . En lugar de dividir la numeración por la denominación, multiplique el numerador por el módulo inverso del denominador, ya que la división no está permitida en el dominio del módulo.
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;
// Function to calculate x^y %mod efficiently
int power(long long x, int y, int mod)
{
// Initialize the answer
long long res = 1;
while (y) {
// If power is odd
if (y & 1)
// Update the answer
res = (res * x) % mod;
// Square the base and half the exponent
x = (x * x) % mod;
y = (y >> 1);
}
// Return the value
return (int)(res % mod);
}
// Function to calculate ncr%mod efficiently
int ncr(int n, int r, int mod)
{
// Initialize the answer
long long res = 1;
// Calculate ncr in O(r)
for (int i = 1; i <= r; i += 1) {
// Multiply with the numerator factor
res = (res * (n - i + 1)) % mod;
// Calculate the inverse of factor of denominator
int inv = power(i, mod - 2, mod);
// Multiply with inverse value
res = (res * inv) % mod;
}
// Return answer value
return (int)(res%mod);
}
// Function to return the number
// of non intersecting chords
int NoOfChords(int A)
{
// define mod value
int mod = 1e9 + 7;
// Value of C(2n, n)
long long ans = ncr(2 * A, A, mod);
// Modulo inverse of (n+1)
int inv = power(A + 1, mod - 2, mod);
// Multiply with modulo inverse
ans = (ans * inv) % mod;
// Return the answer
return (int)(ans%mod);
}
// Driver code
int main()
{
int N = 2;
// Function call
cout << NoOfChords(N);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to calculate x^y %mod efficiently
static int power(long x, int y, int mod)
{
// Initialize the answer
long res = 1;
while (y != 0)
{
// If power is odd
if ((y & 1) == 1)
// Update the answer
res = (res * x) % mod;
// Square the base and half the exponent
x = (x * x) % mod;
y = (y >> 1);
}
// Return the value
return (int)(res % mod);
}
// Function to calculate ncr%mod efficiently
static int ncr(int n, int r, int mod)
{
// Initialize the answer
long res = 1;
// Calculate ncr in O(r)
for (int i = 1; i <= r; i += 1)
{
// Multiply with the numerator factor
res = (res * (n - i + 1)) % mod;
// Calculate the inverse of
// factor of denominator
int inv = power(i, mod - 2, mod);
// Multiply with inverse value
res = (res * inv) % mod;
}
// Return answer value
return (int)(res % mod);
}
// Function to return the number
// of non intersecting chords
static int NoOfChords(int A)
{
// define mod value
int mod = (int)(1e9 + 7);
// Value of C(2n, n)
long ans = ncr(2 * A, A, mod);
// Modulo inverse of (n+1)
int inv = power(A + 1, mod - 2, mod);
// Multiply with modulo inverse
ans = (ans * inv) % mod;
// Return the answer
return (int)(ans % mod);
}
// Driver code
public static void main(String[] args)
{
int N = 2;
// Function call
System.out.println(NoOfChords(N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach # Function to calculate x^y %mod efficiently def power(x, y, mod): # Initialize the answer res = 1 while (y): # If power is odd if (y & 1): # Update the answer res = (res * x) % mod # Square the base and half the exponent x = (x * x) % mod y = (y >> 1) # Return the value return (res % mod) # Function to calculate ncr%mod efficiently def ncr(n, r, mod): # Initialize the answer res = 1 # Calculate ncr in O(r) for i in range(1,r+1): # Multiply with the numerator factor res = (res * (n - i + 1)) % mod # Calculate the inverse of factor of denominator inv = power(i, mod - 2, mod) # Multiply with inverse value res = (res * inv) % mod # Return answer value return (res%mod) # Function to return the number # of non intersecting chords def NoOfChords(A): # define mod value mod = 10**9 + 7 # Value of C(2n, n) ans = ncr(2 * A, A, mod) # Modulo inverse of (n+1) inv = power(A + 1, mod - 2, mod) # Multiply with modulo inverse ans = (ans * inv) % mod # Return the answer return (ans%mod) # Driver code N = 2 # Function call print(NoOfChords(N)) # This code is contributed by mohit kumar 29
C#
// Java implementation of the above approach
using System;
class GFG
{
// Function to calculate x^y %mod efficiently
static int power(long x, int y, int mod)
{
// Initialize the answer
long res = 1;
while (y != 0)
{
// If power is odd
if ((y & 1) == 1)
// Update the answer
res = (res * x) % mod;
// Square the base and half the exponent
x = (x * x) % mod;
y = (y >> 1);
}
// Return the value
return (int)(res % mod);
}
// Function to calculate ncr%mod efficiently
static int ncr(int n, int r, int mod)
{
// Initialize the answer
long res = 1;
// Calculate ncr in O(r)
for (int i = 1; i <= r; i += 1)
{
// Multiply with the numerator factor
res = (res * (n - i + 1)) % mod;
// Calculate the inverse of factor of denominator
int inv = power(i, mod - 2, mod);
// Multiply with inverse value
res = (res * inv) % mod;
}
// Return answer value
return (int)(res % mod);
}
// Function to return the number
// of non intersecting chords
static int NoOfChords(int A)
{
// define mod value
int mod = (int)(1e9 + 7);
// Value of C(2n, n)
long ans = ncr(2 * A, A, mod);
// Modulo inverse of (n+1)
int inv = power(A + 1, mod - 2, mod);
// Multiply with modulo inverse
ans = (ans * inv) % mod;
// Return the answer
return (int)(ans % mod);
}
// Driver code
public static void Main ()
{
int N = 2;
// Function call
Console.WriteLine(NoOfChords(N));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript implementation of the approach
// Function to calculate x^y %mod efficiently
function power(x , y , mod)
{
// Initialize the answer
var res = 1;
while (y != 0)
{
// If power is odd
if ((y & 1) == 1)
// Update the answer
res = (res * x) % mod;
// Square the base and half the exponent
x = (x * x) % mod;
y = (y >> 1);
}
// Return the value
return parseInt(res % mod);
}
// Function to calculate ncr%mod efficiently
function ncr(n , r , mod)
{
// Initialize the answer
var res = 1;
// Calculate ncr in O(r)
for (var i = 1; i <= r; i += 1)
{
// Multiply with the numerator factor
res = (res * (n - i + 1)) % mod;
// Calculate the inverse of
// factor of denominator
var inv = power(i, mod - 2, mod);
// Multiply with inverse value
res = (res * inv) % mod;
}
// Return answer value
return parseInt(res % mod);
}
// Function to return the number
// of non intersecting chords
function NoOfChords( A)
{
// define mod value
var mod = parseInt(7);
// Value of C(2n, n)
var ans = ncr(2 * A, A, mod);
// Modulo inverse of (n+1)
var inv = power(A + 1, mod - 2, mod);
// Multiply with modulo inverse
ans = (ans * inv) % mod;
// Return the answer
return parseInt(ans % mod);
}
// Driver code
var N = 2;
// Function call
document.write(NoOfChords(N));
// This code is contributed by 29AjayKumar
</script>
Producción:
2
Complejidad del tiempo: O(N*log(mod))
Espacio Auxiliar: O(1)