Dado un entero positivo N , la tarea es encontrar el número de relaciones que son relaciones antisimétricas irreflexivas que se pueden formar sobre el conjunto de elementos dado. Dado que el conteo puede ser muy grande, imprímalo en módulo 10 9 + 7 .
Una relación R sobre un conjunto A se llama reflexiva si no se cumple (a, a) € R para todo elemento a € A .
Por ejemplo: si el conjunto A = {a, b} entonces R = {(a, b), (b, a)} es una relación irreflexiva.Una relación R sobre un conjunto A se llama Antisimétrica si y sólo si (a, b) € R y (b, a) € R , entonces a = b se llama antisimétrica, es decir, la relación R = {(a, b) → R | a ≤ b } es antisimétrico, ya que a ≤ b y b ≤ a implica a = b.
Ejemplos:
Entrada: N = 2
Salida: 3
Explicación:
Considerando el conjunto {a, b}, todas las relaciones posibles que son a la vez relaciones irreflexivas y antisimétricas son:
- {}
- {{a,b}}
- {{b, a}}
Entrada: N = 5
Salida: 59049
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Una relación R sobre un conjunto A es un subconjunto del Producto cartesiano de un conjunto, es decir, A * A con N 2 elementos .
- No se debe incluir ningún par (x, x) en el subconjunto para asegurarse de que la relación sea irreflexiva .
- Para los pares restantes (N 2 – N) , divídalos en (N 2 – N)/2 grupos donde cada grupo consiste en un par (x, y) y su par simétrico (y, x) .
- Ahora, hay tres opciones , incluir uno de los pares ordenados o ninguno de ellos de un grupo.
- Por lo tanto, el número total de relaciones posibles que son a la vez irreflexivas y antisimétricas está dado por 3 (N2 – N)/2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
const int mod = 1000000007;
// Function to calculate
// x ^ y % mod in O(log y)
int power(long long x,
unsigned int y)
{
// Stores the result of x^y
int res = 1;
// Update x if it exceeds mod
x = x % mod;
while (y > 0) {
// If y is odd, then multiply
// x with result
if (y & 1)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the value of x^y
return res;
}
// Function to count relations that
// are irreflexive and antisymmetric
// in a set consisting of N elements
int numberOfRelations(int N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
int main()
{
int N = 2;
cout << numberOfRelations(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int mod = 1000000007;
// Function to calculate
// x ^ y % mod in O(log y)
static int power(long x, int y)
{
// Stores the result of x^y
int res = 1;
// Update x if it exceeds mod
x = x % mod;
while (y > 0)
{
// If y is odd, then multiply
// x with result
if (y % 2 == 1)
res = (int)(res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the value of x^y
return res;
}
// Function to count relations that
// are irreflexive and antisymmetric
// in a set consisting of N elements
static int numberOfRelations(int N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
public static void main(String[] args)
{
int N = 2;
System.out.print(numberOfRelations(N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach mod = 1000000007 # Function to calculate # x ^ y % mod in O(log y) def power(x, y): # Stores the result of x^y res = 1 # Update x if it exceeds mod x = x % mod while (y > 0): # If y is odd, then multiply # x with result if (y & 1): res = (res * x) % mod # Divide y by 2 y = y >> 1 # Update the value of x x = (x * x) % mod # Return the value of x^y return res # Function to count relations that # are irreflexive and antisymmetric # in a set consisting of N elements def numberOfRelations(N): # Return the resultant count return power(3, (N * N - N) // 2) # Driver Code if __name__ == "__main__": N = 2 print(numberOfRelations(N)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG{
static int mod = 1000000007;
// Function to calculate
// x ^ y % mod in O(log y)
static int power(long x, int y)
{
// Stores the result of x^y
int res = 1;
// Update x if it exceeds mod
x = x % mod;
while (y > 0)
{
// If y is odd, then multiply
// x with result
if (y % 2 == 1)
res = (int)(res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the value of x^y
return res;
}
// Function to count relations that
// are irreflexive and antisymmetric
// in a set consisting of N elements
static int numberOfRelations(int N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
public static void Main(String[] args)
{
int N = 2;
Console.Write(numberOfRelations(N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approach
let mod = 1000000007;
// Function to calculate
// x ^ y % mod in O(log y)
function power(x, y)
{
// Stores the result of x^y
let res = 1;
// Update x if it exceeds mod
x = x % mod;
while (y > 0) {
// If y is odd, then multiply
// x with result
if (y & 1)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the value of x^y
return res;
}
// Function to count relations that
// are irreflexive and antisymmetric
// in a set consisting of N elements
function numberOfRelations(N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
let N = 2;
document.write(numberOfRelations(N));
</script>
3
Complejidad de Tiempo: O(log N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA