Dado un entero positivo N , la tarea es encontrar el número de relaciones antisimétricas en el conjunto dado de N elementos. Dado que el número de relaciones puede ser muy grande, imprímalo módulo 10 9 +7 .
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: 12
Explicación: Considerando el conjunto {a, b}, todas las posibles relaciones antisimétricas son:
{}, {(a, b)}, {(b, a)}, {(a, a) }, {(a, a), (a, b)}, {(a, a), (b, a)}, {(b, b)}, {(b, b), (a, b) }, {(b, b), (b, a)}, {(a, a), (b, b)}, {(a, a), (b, b), (a, b)}, {(a, a), (b, b), (b, a)}.Entrada: N = 5
Salida: 1889568
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Considerando una relación antisimétrica R en el conjunto S, digamos a , b ∈ A con a ≠ b, entonces la relación R no debe contener tanto (a, b) como (b, a) . Puede contener uno de los pares ordenados o ninguno de ellos.
- Hay 3 opciones posibles para todos los pares.
- Por lo tanto, el recuento de todas las combinaciones de estas opciones es igual a 3 (N*(N – 1))/2 .
- El número de subconjuntos de pares de la forma (a, a) es igual a 2 N .
Por lo tanto, el recuento total de posibles relaciones antisimétricas es igual a 2 N * 3 (N*(N – 1))/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 the
// value of 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 resultant
// value of x^y
return res;
}
// Function to count the number of
// antisymmetric relations in a set
// consisting of N elements
int antisymmetricRelation(int N)
{
// Print the count of
// antisymmetric relations
return (power(2, N) * 1LL * power(3, (N * N - N) / 2)) % mod;
}
// Driver Code
int main()
{
int N = 2;
cout << antisymmetricRelation(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int mod = 1000000007;
// Function to calculate the
// value of x ^ y % mod in O(log y)
static int power(int 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 & 1) != 0)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the resultant
// value of x^y
return res;
}
// Function to count the number of
// antisymmetric relations in a set
// consisting of N elements
static int antisymmetricRelation(int N)
{
// Print the count of
// antisymmetric relations
return (power(2, N) *
power(3, (N * N - N) / 2)) % mod;
}
// Driver Code
public static void main(String []args)
{
int N = 2;
System.out.print(antisymmetricRelation(N));
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program for the above approach mod = 1000000007 # Function to calculate the # value of 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 resultant # value of x^y return res # Function to count the number of # antisymmetric relations in a set # consisting of N elements def antisymmetricRelation(N): # Print the count of # antisymmetric relations return (power(2, N) * power(3, (N * N - N) // 2)) % mod # Driver Code if __name__ == "__main__": N = 2 print(antisymmetricRelation(N)) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int mod = 1000000007;
// Function to calculate the
// value of x ^ y % mod in O(log y)
static int power(int 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 & 1)>0)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the resultant
// value of x^y
return res;
}
// Function to count the number of
// antisymmetric relations in a set
// consisting of N elements
static int antisymmetricRelation(int N)
{
// Print the count of
// antisymmetric relations
return (power(2, N) *
power(3, (N * N - N) / 2)) % mod;
}
// Driver Code
public static void Main()
{
int N = 2;
Console.Write(antisymmetricRelation(N));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
var mod = 1000000007;
// Function to calculate the
// value of x ^ y % mod in O(log y)
function power(x, y)
{
// Stores the result of x^y
var 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 resultant
// value of x^y
return res;
}
// Function to count the number of
// antisymmetric relations in a set
// consisting of N elements
function antisymmetricRelation(N)
{
// Print the count of
// antisymmetric relations
return (power(2, N) * power(3, (N * N - N) / 2)) % mod;
}
// Driver Code
var N = 2;
document.write( antisymmetricRelation(N));
</script>
12
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA