Dada una array arr[] de segmentos de línea en el eje x y un número entero K , la tarea es calcular el número de formas de elegir los K segmentos de línea para que se crucen en cualquier punto. Como la respuesta puede ser grande, imprímela en módulo 10^9+7.
Ejemplos:
Entrada: arr[] = [[1, 3], [4, 5], [5, 7]], K = 2
Salida: 2
Explicación:
La primera forma de elegir [1, 3], [4, 5] y la segunda forma es [1, 3], [5, 7]. Dado que la intersección de [4, 5], [5, 7] no es cero y, por lo tanto, no se puede incluir en la respuesta.Entrada: [[3, 7], [1, 4], [6, 9], [8, 13], [9, 11]], K = 1
Salida: 0
Explicación:
Dado que solo estamos buscando una sola línea segmento, pero para cada segmento de línea individual, la intersección siempre no está vacía.
Planteamiento:
Para resolver el problema mencionado anteriormente, intentaremos encontrar el número de casos impares, es decir, aquellos casos cuya intersección no está vacía. Así que claramente nuestra respuesta será Caso Total – Caso Impar.
Para calcular el número total de casos, se sigue el siguiente enfoque:
- Los casos totales que son posibles son “n elige k” o n C k
- Precalculamos el inverso y el factorial de los números requeridos para calcular n C k
- en tiempo O(1)
- El segmento de línea K se interseca como si min(R1, R2, .., R{k-1}) >= Li donde se está considerando el segmento de línea [Li, Ri]. Mantener un multiset, para mantener el orden. En primer lugar, ordene los segmentos en orden creciente de Li. Si Li son iguales, entonces el segmento con Ri más pequeño viene primero.
Para cada segmento de línea [Li, Ri], se sigue el siguiente enfoque para encontrar el número de casos impares.
- Si bien multiset no está vacío y las líneas no se cruzan, elimine la línea con el Ri más pequeño de multiset y verifique nuevamente.
- Número de formas violatorias usando este segmento [Li, Ri] son p C k-1
- donde p = tamaño_de_multiconjunto.
- Inserte el punto final de este segmento de línea en el conjunto múltiple.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Number of ways // to choose K intersecting // line segments on X-axis #include <bits/stdc++.h> using namespace std; const long long mod = 1000000007; const int MAXN = 1001; long long factorial[MAXN], inverse[MAXN]; // Function to find (a^b)%mod in log b long long power(long long a, long long b) { long long res = 1; // Till power becomes 0 while (b > 0) { // If power is odd if (b % 2 == 1) { res = (res * a) % mod; } // Multiply base a = (a * a) % mod; // Divide power by 1 b >>= 1; } return res; } // Function to find nCk long long nCk(int n, int k) { // Base case if (k < 0 || k > n) { return 0; } // Apply formula to find nCk long long ans = factorial[n]; ans = (ans * inverse[n - k]) % mod; ans = (ans * inverse[k]) % mod; return ans; } // Function to find the number of ways void numberOfWays(vector<pair<int, int> > lines, int K, int N) { // sort the given lines sort(lines.begin(), lines.end()); // Find the number of total case long long total_case = nCk(N, K); // Declare a multiset multiset<int> m; // loop till N for (int i = 0; i < N; i++) { // Check if smallest element is // smaller than lines[i] while (!m.empty() && (*m.begin() < lines[i].first)) { // Erase first element m.erase(m.begin()); } // Exclude the odd cases total_case -= nCk(m.size(), K - 1); // Modulus operation total_case += mod; total_case %= mod; // Insert into multiset m.insert(lines[i].second); } cout << total_case << endl; } // Function to precompute // factorial and inverse void preCompute() { long long fact = 1; factorial[0] = 1; inverse[0] = 1; // Pre-compute factorial and inverse for (int i = 1; i < MAXN; i++) { fact = (fact * i) % mod; factorial[i] = fact; inverse[i] = power(factorial[i], mod - 2); } } // Driver code int main() { int N = 3, K = 2; vector<pair<int, int> > lines; // Function to pre-compute // factorial and inverse preCompute(); lines.push_back({ 1, 3 }); lines.push_back({ 4, 5 }); lines.push_back({ 5, 7 }); numberOfWays(lines, K, N); return 0; }
Java
// Java program to find Number of ways // to choose K intersecting line // segments on X-axis import java.util.*; import java.lang.*; class GFG { static long mod = 1000000007; static int MAXN = 1001; static long factorial[] = new long[MAXN], inverse[] = new long[MAXN]; // Function to find (a^b)%mod in log b static long power(long a, long b) { long res = 1; // Till power becomes 0 while (b > 0) { // If power is odd if (b % 2 == 1) { res = (res * a) % mod; } // Multiply base a = (a * a) % mod; // Divide power by 1 b >>= 1; } return res; } // Function to find nCk static long nCk(int n, int k) { // Base case if (k < 0 || k > n) { return 0; } // Apply formula to find nCk long ans = factorial[n]; ans = (ans * inverse[n - k]) % mod; ans = (ans * inverse[k]) % mod; return ans; } // Function to find the number of ways static void numberOfWays(ArrayList<int[]> lines, int K, int N) { // sort the given lines Collections.sort(lines, (a, b) -> a[0] - b[0]); // Find the number of total case long total_case = nCk(N, K); // Declare a multiset PriorityQueue<Integer> m = new PriorityQueue<>(); // Loop till N for (int i = 0; i < N; i++) { // Check if smallest element is // smaller than lines[i] while (!m.isEmpty() && (m.peek() < lines.get(i)[0])) { // Erase first element m.poll(); } // Exclude the odd cases total_case -= nCk(m.size(), K - 1); // Modulus operation total_case += mod; total_case %= mod; // Insert into multiset m.add(lines.get(i)[1]); } System.out.println(total_case); } // Function to precompute // factorial and inverse static void preCompute() { long fact = 1; factorial[0] = 1; inverse[0] = 1; // Pre-compute factorial and inverse for (int i = 1; i < MAXN; i++) { fact = (fact * i) % mod; factorial[i] = fact; inverse[i] = power(factorial[i], mod - 2); } } // Driver code public static void main(String[] args) { int N = 3, K = 2; ArrayList<int[]> lines = new ArrayList<>(); // Function to pre-compute // factorial and inverse preCompute(); lines.add(new int[] { 1, 3 }); lines.add(new int[] { 4, 5 }); lines.add(new int[] { 5, 7 }); numberOfWays(lines, K, N); } } // This code is contributed by offbeat
Python3
# Python3 program to find Number of ways # to choose K ersecting # line segments on X-axis import heapq as hq mod = 1000000007 MAXN = 1001 factorial=[1]*MAXN; inverse=[1]*MAXN # Function to find (a^b)%mod in log b def power(a, b): res = 1 # Till power becomes 0 while (b > 0) : # If power is odd if (b % 2 == 1) : res = (res * a) % mod # Multiply base a = (a * a) % mod # Divide power by 1 b >>= 1 return res # Function to find nCk def nCk(n, k): # Base case if (k < 0 or k > n) : return 0 # Apply formula to find nCk ans = factorial[n] ans = (ans * inverse[n - k]) % mod ans = (ans * inverse[k]) % mod return ans # Function to find the number of ways def numberOfWays(lines, K, N): # sort the given lines lines.sort() # Find the number of total case total_case = nCk(N, K) # Declare a heap m=[] # loop till N for i in range(N): # Check if smallest element is # smaller than lines[i] while (m and m[0] < lines[i][0]): # Erase first element hq.heappop(m) # Exclude the odd cases total_case -= nCk(len(m), K - 1) # Modulus operation total_case += mod total_case %= mod # Insert into heap hq.heappush(m,lines[i][1]) print(total_case) # Function to precompute # factorial and inverse def preCompute(): global factorial fact = 1 factorial[0] = 1 inverse[0] = 1 # Pre-compute factorial and inverse for i in range(1,MAXN) : fact = (fact * i) % mod factorial[i] = fact inverse[i] = power(factorial[i], mod - 2) # Driver code if __name__ == '__main__': N = 3; K = 2 lines=[] # Function to pre-compute # factorial and inverse preCompute() lines.append((1, 3)) lines.append((4, 5)) lines.append((5, 7)) numberOfWays(lines, K, N)
2
Complejidad de tiempo: O(MAXN * log(MAXN) + N * log(N)).
Espacio Auxiliar: O(MAXN + N).
Publicación traducida automáticamente
Artículo escrito por uditkhemka64 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA