Dado un entero positivo N , la tarea es encontrar el número de Relaciones Asimétricas en un conjunto 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 Asimétrica si y sólo si existe x R y , entonces y
Rx para cada (x, y) € A .
Por ejemplo: si el conjunto A = {a, b}, entonces R = {(a, b)} es una relación asimétrica.
Ejemplos:
Entrada: N = 2
Salida: 3
Explicación: Considerando el conjunto {1, 2}, el número total de relaciones asimétricas posibles son {{}, {(1, 2)}, {(2, 1)}}.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.
- Hay un total de N pares de tipo (x, x) que están presentes en el producto cartesiano, donde cualquiera de (x, x) no debe incluirse en el subconjunto.
- Ahora, uno se queda con (N 2 – N) elementos del producto cartesiano.
- Para satisfacer la propiedad de la relación asimétrica, uno tiene tres posibilidades de incluir solo de tipo (x, y) o solo de tipo (y, x) o ninguno de un solo grupo en el subconjunto.
- Por tanto, el número total de posibles relaciones asimétricas es igual a 3 (N2 – N) / 2 .
Por lo tanto, la idea es imprimir el valor de 3 (N2 – N)/2 módulo 10 9 + 7 como resultado.
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 modulo (10^9 + 7)
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;
// If x is divisible by mod
if (x == 0)
return 0;
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 final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
int asymmetricRelation(int N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
int main()
{
int N = 2;
cout << asymmetricRelation(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
final static int mod = 1000000007;
// Function to calculate
// x^y modulo (10^9 + 7)
public 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;
// If x is divisible by mod
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd, then
// multiply x with result
if (y % 2 == 1)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
public static int asymmetricRelation(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(asymmetricRelation(N));
}
}
// This code is contributed by user_qa7r
Python3
# Python3 program for the above approach mod = 1000000007 # Function to calculate # x^y modulo (10^9 + 7) def power(x, y): # Stores the result of x^y res = 1 # Update x if it exceeds mod x = x % mod # If x is divisible by mod if (x == 0): return 0 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 final # value of x ^ y return res # Function to count the number of # asymmetric relations in a set # consisting of N elements def asymmetricRelation(N): # Return the resultant count return power(3, (N * N - N) // 2) # Driver Code if __name__ == '__main__': N = 2 print(asymmetricRelation(N)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
const int mod = 1000000007;
// Function to calculate
// x^y modulo (10^9 + 7)
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;
// If x is divisible by mod
if (x == 0)
return 0;
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 final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
static int asymmetricRelation(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.WriteLine(asymmetricRelation(N));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
var mod = 1000000007;
// Function to calculate
// x^y modulo (10^9 + 7)
function power(x, y)
{
// Stores the result of x^y
var res = 1;
// Update x if it exceeds mod
x = x % mod;
// If x is divisible by mod
if (x == 0)
return 0;
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 final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
function asymmetricRelation( N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
var N = 2;
document.write( asymmetricRelation(N));
</script>
Producción:
3
Complejidad de tiempo: O(N*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