Dado un entero positivo N , la tarea es encontrar el número de relaciones 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.
Ejemplos:
Entrada: N = 2
Salida: 4
Explicación:
Considerando el conjunto {1, 2}, el total de relaciones irreflexivas posibles son:
- {}
- {(1, 2)}
- {(2, 1)}
- {(1, 2), (2, 1)}
Entrada: N = 5
Salida: 1048576
Enfoque: siga los pasos a continuación para resolver el problema:
- 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.
- Relación Irreflexiva: Una relación R sobre un conjunto A se llama Irreflexiva si y sólo si x
Rx [(x, x) no pertenece a R] para todo elemento x en A . - Hay un total de N pares de (x, x) presentes en el producto cartesiano que no deben incluirse en una relación irreflexiva. Por lo tanto, para los elementos restantes (N 2 – N) , cada elemento tiene dos opciones, es decir, incluirlo o excluirlo del subconjunto.
- Por lo tanto, el número total de posibles relaciones irreflexivas viene dado por 2 (N2 – N) .
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 1000000007 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;
// 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 resultant value of x^y
return res;
}
// Function to count the number of
// irreflixive relations in a set
// consisting of N elements
int irreflexiveRelation(int N)
{
// Return the resultant count
return power(2, N * N - N);
}
// Driver Code
int main()
{
int N = 2;
cout << irreflexiveRelation(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
static int mod = 1000000007;
// Function to calculate x^y
// modulo 1000000007 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;
// 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 resultant value of x^y
return res;
}
// Function to count the number of
// irreflixive relations in a set
// consisting of N elements
static int irreflexiveRelation(int N)
{
// Return the resultant count
return power(2, N * N - N);
}
// Driver Code
public static void main(String[] args)
{
int N = 2;
System.out.println(irreflexiveRelation(N));
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach mod = 1000000007 # Function to calculate x^y # modulo 1000000007 in O(log y) def power(x, y): global mod # 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 resultant value of x^y return res # Function to count the number of # irreflixive relations in a set # consisting of N elements def irreflexiveRelation(N): # Return the resultant count return power(2, N * N - N) # Driver Code if __name__ == '__main__': N = 2 print(irreflexiveRelation(N)) # This code is contributed by mohit kumar 29.
C#
// C# program for above approach
using System;
public class GFG
{
static int mod = 1000000007;
// Function to calculate x^y
// modulo 1000000007 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;
// 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 resultant value of x^y
return res;
}
// Function to count the number of
// irreflixive relations in a set
// consisting of N elements
static int irreflexiveRelation(int N)
{
// Return the resultant count
return power(2, N * N - N);
}
// Driver code
public static void Main(String[] args)
{
int N = 2;
Console.WriteLine(irreflexiveRelation(N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
let mod = 1000000007;
// Function to calculate x^y
// modulo 1000000007 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;
// 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 resultant value of x^y
return res;
}
// Function to count the number of
// irreflixive relations in a set
// consisting of N elements
function irreflexiveRelation(N)
{
// Return the resultant count
return power(2, N * N - N);
}
// Driver code
let N = 2;
document.write(irreflexiveRelation(N));
</script>
Producción:
4
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