Recuento de todos los posibles pares de subconjuntos disjuntos de enteros del 1 al N

Dado un número entero N. Considere el conjunto de primeros N números naturales A = {1, 2, 3, …, N} . Sean M y P dos subconjuntos no vacíos de A. La tarea es contar el número de pares no ordenados de (M, P) tales que M y P sean conjuntos disjuntos . Tenga en cuenta que el orden de M y P no importa.

Ejemplos:

Entrada: N = 3
Salida: 6
Los pares no ordenados son ({1}, {2}), ({1}, {3}),
({2}, {3}), ({1}, {2, 3}), ({2}, {1, 3}), ({3}, {1, 2}).

Entrada: N = 2
Salida: 1

Entrada: N = 10
Salida: 28501

Acercarse:

1. Supongamos que solo hay 6 elementos en el conjunto {1, 2, 3, 4, 5, 6}.
2. Cuando cuenta el número de subconjuntos con 1 como uno de los elementos del primer subconjunto, resulta ser 211.
3. Contando el número de subconjuntos con 2 siendo uno de los elementos del primer subconjunto, resulta ser 65, porque 1 no está incluido ya que el orden de los conjuntos no importa.
4. Contando el número de subconjuntos con 3 siendo uno de los elementos del primer conjunto resulta ser 65, aquí se puede observar un patrón.
5. Patrón:
   

   5 = 3 * 1 + 2
   19 = 3 * 5 + 4
   65 = 3 * 19 + 8
   211 = 3 * 65 + 16
   S(n) = 3 * S(n-1) + 2 ^{(n – 2)}

6. Expandiéndolo hasta n->2 (significa números de elementos n-2+1=n-1)
   2 ^(n-2) * 3 ⁽⁰⁾ + 2 ^{(n – 3)} * 3 ¹ + 2 ^{(n – 4)} * 3 ² + 2 ^{(n – 5)} * 3 ³ + … + 2 ⁽⁰⁾ * 3 ^{(n – 2)}
   De la progresión geométrica, a + a * r ⁰ + a * r ¹ + … + a * r ^{(n – 1)} = un * (r ⁿ – 1) / (r – 1)
7. S(n) = 3 ^{(n – 1)} – 2 ^{(n – 1)} . Recuerde que S(n) es un número de subconjuntos con 1 como uno de los elementos del primer subconjunto, pero para obtener el resultado requerido, denotado por T(n) = S(1) + S(2) + S(3) + … +S(n)
8. También forma una progresión geométrica, por lo que la calculamos con la fórmula de la suma de GP
   T(n) = (3 ⁿ – 2 ^{n + 1} + 1)/2
9. Como requerimos T(n) % p donde p = 10 ⁹ + 7
   Tenemos que usar el pequeño teorema de Fermats
   a ^-1 = a ^{(m – 2)} (mod m) para la división modular

   A continuación se muestra la implementación del enfoque anterior:

   C++

   // C++ implementation of the approach    #include <bits/stdc++.h> using namespace std; #define p 1000000007    // Modulo exponentiation function long long power(long long x, long long y) {     // Function to calculate (x^y)%p in O(log(y))     long long res = 1;     x = x % p;        while (y > 0) {         if (y & 1)             res = (res * x) % p;         y = y >> 1;         x = (x * x) % p;     }        return res % p; }    // Driver function int main() {     long long n = 3;        // Evaluating ((3^n-2^(n+1)+1)/2)%p     long long x = (power(3, n) % p + 1) % p;        x = (x - power(2, n + 1) + p) % p;        // From  Fermats’s little theorem     // a^-1 ? a^(m-2) (mod m)        x = (x * power(2, p - 2)) % p;     cout << x << "\n"; }

   Java

   // Java implementation of the approach class GFG  {  static int p = 1000000007;    // Modulo exponentiation function static long power(long x, long y) {     // Function to calculate (x^y)%p in O(log(y))     long res = 1;     x = x % p;        while (y > 0)     {         if (y % 2 == 1)             res = (res * x) % p;         y = y >> 1;         x = (x * x) % p;     }     return res % p; }    // Driver Code public static void main(String[] args)  {     long n = 3;        // Evaluating ((3^n-2^(n+1)+1)/2)%p     long x = (power(3, n) % p + 1) % p;        x = (x - power(2, n + 1) + p) % p;        // From Fermats's little theorem     // a^-1 ? a^(m-2) (mod m)        x = (x * power(2, p - 2)) % p;     System.out.println(x); } }    // This code is contributed by Rajput-Ji

   Python3

   # Python3 implementation of the approach p = 1000000007    # Modulo exponentiation function def power(x, y):            # Function to calculate (x^y)%p in O(log(y))     res = 1     x = x % p        while (y > 0):         if (y & 1):             res = (res * x) % p;         y = y >> 1         x = (x * x) % p        return res % p    # Driver Code n = 3    # Evaluating ((3^n-2^(n+1)+1)/2)%p x = (power(3, n) % p + 1) % p    x = (x - power(2, n + 1) + p) % p    # From Fermats’s little theorem # a^-1 ? a^(m-2) (mod m) x = (x * power(2, p - 2)) % p    print(x)    # This code is contributed by Mohit Kumar

   C#

   // C# implementation of the approach using System;    class GFG { static int p = 1000000007;    // Modulo exponentiation function static long power(long x, long y) {     // Function to calculate (x^y)%p in O(log(y))     long res = 1;     x = x % p;        while (y > 0)     {         if (y % 2 == 1)             res = (res * x) % p;         y = y >> 1;         x = (x * x) % p;     }     return res % p; }    // Driver Code static public void Main() {     long n = 3;            // Evaluating ((3^n-2^(n+1)+1)/2)%p     long x = (power(3, n) % p + 1) % p;            x = (x - power(2, n + 1) + p) % p;            // From Fermats's little theorem     // a^-1 ? a^(m-2) (mod m)            x = (x * power(2, p - 2)) % p;     Console.Write(x); } }    // This code is contributed by ajit.

   Producción:

   6