Encuentre la cantidad de strings que se pueden formar después de procesar las consultas Q

Dado un número N (1<=N<=2000), la tarea es encontrar las strings de números de tamaño N que se pueden obtener después de usar caracteres de ‘a’ a ‘z’ y procesando el q dado ( 1 < =q<=200000) consultas.

Para cada consulta dados dos enteros L, R (0<=L<=R<=N) tales que la substring [L, R] de la string generada de tamaño N debe ser un palíndromo. La tarea es procesar todas las consultas y generar una string de tamaño N tal que las substrings de esta string definidas por todas las consultas sean palíndromos.

La respuesta puede ser muy grande. Entonces, salida módulo de respuesta 1000000007.

Nota : la indexación basada en 1 se considera para la string.

Ejemplos:

Input : N = 3
query 1: (1, 2)
query 2: (2, 3)
Output : 26
Explanation : Substring 1 to 2 should be 
palindrome and substring 2 to 3 should be palindrome. so, all 
three characters should be same. so, we can obtain 26 such strings.

Input : N = 4
query 1: (1, 3)
query 2: (2, 4)
Output : 676
Explanation : substring 1 to 3 should be 
palindrome and substring 2 to 4 should be a palindrome. 
So, a first and third character should be the same and 
second and the fourth should be the same. So, we can 
obtain 26*26 such strings.

Enfoque : una solución eficiente es utilizar el algoritmo de búsqueda de unión .

• Encuentre el punto medio de cada rango (consulta) y si hay muchas consultas que tienen el mismo punto medio, solo conserve la consulta cuya longitud sea máxima, es decir (donde r – l es máxima).
• Esto habría reducido el número de consultas a 2*N como máximo, ya que hay un número de 2*N de puntos medios en una string de longitud N.
• Ahora, para cada consulta, haga la unión del elemento l con r, (l + 1) con (r – 1), (l + 2) con (r – 2) y así sucesivamente. Hacemos esto porque el carácter que se colocaría en el índice l sería el mismo que se colocaría en el índice r. Al extender esta lógica a todas las consultas, necesitamos mantener una estructura de datos de conjuntos disjuntos . Entonces, básicamente, todos los elementos de un componente de un conjunto disjunto deben tener la misma letra.
• Después de procesar todas las consultas, sea x el número de componentes del conjunto disjunto, entonces la respuesta es 26^x

.

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

C++

// C++ program to implement above approach    #include <bits/stdc++.h> using namespace std; #define N 2005 #define mod (int)(1e9 + 7)    // To store the size of string and // number of queries int n, q;    // To store parent and rank of ith place int par[N], Rank[N];    // To store maximum interval map<int, int> m;    // Function for initialization void initialize() {     for (int i = 0; i <= n; i++) {         par[i] = i;         Rank[i] = 0;     } }    // Function to find parent int find(int x) {     if (par[x] != x)         par[x] = find(par[x]);        return par[x]; }    // Function to make union void Union(int x, int y) {     int xpar = find(x);     int ypar = find(y);        if (Rank[xpar] < Rank[ypar])         par[xpar] = ypar;     else if (Rank[xpar] > Rank[ypar])         par[ypar] = xpar;     else {         par[ypar] = xpar;         Rank[xpar]++;     } }    // Power function to calculate a raised to m1 // under modulo 10000007 int power(long long a, long long m1) {     if (m1 == 0)         return 1;     else if (m1 == 1)         return a;     else if (m1 == 2)         return (1LL * a * a) % mod;     else if (m1 & 1)         return (1LL * a * power(power(a, m1 / 2), 2)) % mod;     else         return power(power(a, m1 / 2), 2) % mod; }    // Function to take maxmium interval void query(int l, int r) {     m[l + r] = max(m[l + r], r); }    // Function to find different possible strings int possiblestrings() {     initialize();        for (auto i = m.begin(); i != m.end(); i++) {         int x = i->first - i->second;         int y = i->second;            // make union of all chracters which         // are meant to be same         while (x < y) {             Union(x, y);             x++;             y--;         }     }        // find number of different sets formed     int ans = 0;     for (int i = 1; i <= n; i++)         if (par[i] == i)             ans++;        // return the required answer     return power(26, ans) % mod; }    // Driver Code int main() {     n = 4;        // queries     query(1, 3);     query(2, 4);        cout << possiblestrings();        return 0; }

Java

// Java program to implement above approach import java.util.*;    class GFG  {     static final int N = 2005;     static final int mod = 1000000007;        // To store the size of string and     // number of queries     static int n, q;        // To store parent and rank of ith place     static int[] par = new int[N], Rank = new int[N];        // To store maximum interval     static HashMap<Integer,                    Integer> m = new HashMap<>();        // Function for initialization     static void initialize()     {         for (int i = 0; i <= n; i++)         {             par[i] = i;             Rank[i] = 0;         }     }        // Function to find parent     static int find(int x)     {         if (par[x] != x)             par[x] = find(par[x]);            return par[x];     }        // Function to make union     static void Union(int x, int y)      {         int xpar = find(x);         int ypar = find(y);            if (Rank[xpar] < Rank[ypar])             par[xpar] = ypar;         else if (Rank[xpar] > Rank[ypar])             par[ypar] = xpar;         else          {             par[ypar] = xpar;             Rank[xpar]++;         }     }        // Power function to calculate a raised to m1     // under modulo 10000007     static long power(long a, long m1)      {         if (m1 == 0)             return 1;         else if (m1 == 1)             return a;         else if (m1 == 2)             return (1L * a * a) % mod;         else if (m1 % 2 == 1)             return (1L * a * power(power(a, m1 / 2), 2)) % mod;         else             return power(power(a, m1 / 2), 2) % mod;     }        // Function to take maxmium interval     static void query(int l, int r)     {         if (m.containsKey(l + r))             m.put(l + r, Math.max(m.get(l + r), r));         else             m.put(l + r, r);     }        // Function to find different possible strings     static long possiblestrings()      {         initialize();            for (Integer i : m.keySet())         {             int x = i - m.get(i);             int y = m.get(i);                // make union of all chracters which             // are meant to be same             while (x < y)              {                 Union(x, y);                 x++;                 y--;             }         }            // find number of different sets formed         int ans = 0;         for (int i = 1; i <= n; i++)             if (par[i] == i)                 ans++;            // return the required answer         return power(26, ans) % mod;     }        // Driver Code     public static void main(String[] args)      {         n = 4;            // queries         query(1, 3);         query(2, 4);            System.out.println(possiblestrings());     } }    // This code is contributed by // sanjeev2552

Python3

# Python3 program to implement above approach N = 2005 mod = 10**9 + 7    # To store the size of string and # number of queries n, q = 0, 0    # To store parent and rank of ith place par = [0 for i in range(N)] Rank = [0 for i in range(N)]    # To store maximum interval m = dict()    # Function for initialization def initialize():        for i in range(n + 1):         Rank[i], par[i] = 0, i    # Function to find parent def find(x):     if (par[x] != x):         par[x] = find(par[x])        return par[x]    # Function to make union def Union(x, y):        xpar = find(x)     ypar = find(y)        if (Rank[xpar] < Rank[ypar]):         par[xpar] = ypar     elif (Rank[xpar] > Rank[ypar]):         par[ypar] = xpar     else:         par[ypar] = xpar         Rank[xpar] += 1    # Power function to calculate a raised to m1 # under modulo 10000007 def power(a, m1):        if (m1 == 0):         return 1     elif (m1 == 1):         return a     elif (m1 == 2):         return (a * a) % mod     elif (m1 & 1):         return (a * power(power(a, m1 // 2), 2)) % mod     else:         return power(power(a, m1 // 2), 2) % mod    # Function to take maxmium interval def query(l, r):     if l + r in m.keys():         m[l + r] = max(m[l + r], r)     else:         m[l + r] = max(0, r)    # Function to find different possible strings def possiblestrings():     initialize()        for i in m:         x = i - m[i]         y = m[i]            # make union of all chracters which         # are meant to be same         while (x < y):             Union(x, y)             x += 1             y -= 1        # find number of different sets formed     ans = 0     for i in range(1, n + 1):         if (par[i] == i):             ans += 1        # return the required answer     return power(26, ans) % mod    # Driver Code n = 4    # queries query(1, 3) query(2, 4)    print(possiblestrings())    # This code is contributed by Mohit Kumar

C#

// C# program to implement above approach using System; using System.Collections.Generic;     class GFG{        const int N = 2005; const int mod = 1000000007;    // To store the size of string and // number of queries static int n; //static int q;    // To store parent and rank of ith place static int[]par = new int[N]; static int[]Rank = new int[N];    // To store maximum interval static Dictionary<int,                   int> m = new Dictionary<int,                                           int>();    // Function for initialization static void initialize() {     for(int i = 0; i <= n; i++)     {         par[i] = i;         Rank[i] = 0;     } }    // Function to find parent static int find(int x) {     if (par[x] != x)         par[x] = find(par[x]);        return par[x]; }    // Function to make union static void Union(int x, int y)  {     int xpar = find(x);      int ypar = find(y);         if (Rank[xpar] < Rank[ypar])          par[xpar] = ypar;      else if (Rank[xpar] > Rank[ypar])          par[ypar] = xpar;      else     {          par[ypar] = xpar;          Rank[xpar]++;      }  }    // Power function to calculate a raised to m1 // under modulo 10000007 static long power(long a, long m1)  {     if (m1 == 0)         return 1;     else if (m1 == 1)         return a;     else if (m1 == 2)         return (1L * a * a) % mod;     else if (m1 % 2 == 1)         return (1L * a * power(                power(a, m1 / 2), 2)) % mod;     else         return power(power(a, m1 / 2), 2) % mod; }    // Function to take maxmium interval static void query(int l, int r) {     if (m.ContainsKey(l + r))         m[l + r] = Math.Max(m[l + r], r);     else         m[l + r] = r; }    // Function to find different possible strings static long possiblestrings()  {     initialize();        foreach(KeyValuePair<int, int> i in m)     {         int x = i.Key - m[i.Key];         int y = m[i.Key];            // Make union of all chracters          // which are meant to be same         while (x < y)          {             Union(x, y);             x++;             y--;         }     }        // Find number of different sets formed     int ans = 0;     for(int i = 1; i <= n; i++)         if (par[i] == i)             ans++;        // Return the required answer     return power(26, ans) % mod; }    // Driver Code public static void Main(string[] args)  {     n = 4;        // Queries     query(1, 3);     query(2, 4);        Console.Write(possiblestrings()); } }       // This code is contributed by rutvik_56

Producción:

676