Dada una array de enteros arr[] de N elementos distintos y un entero positivo K ( K <= N ). La tarea es calcular el producto de todos los subconjuntos ordenados de tamaño K, de la array dada, usando elementos cuyo índice divide K completamente.
Nota: Como la respuesta puede ser muy grande, imprímela módulo 10^9+7.
Ejemplos:
Entrada: arr[] = {4, 7, 5, 9, 3}, K = 4
Salida: 808556639
Explicación:
En este caso hay 5 conjuntos posibles:
{4, 7, 5, 9} -> 180 (Orden ordenado {4, 5, 7, 9}: el índice 1, 2 y 4 divide a M, por lo que el valor del conjunto es 4 * 5 * 9 = 180)
{4, 7, 9, 3} -> 108
{4, 5, 9 , 3} -> 108
{4, 7, 5, 3} -> 84
{7, 5, 9, 3} -> 135
Valor total = ( 180 * 108 * 108 * 84 * 135 ) % (10 9 +7 ) = 808556639Entrada: arr[] = {7, 8, 9}, K = 2
Salida: 254016
Enfoque ingenuo:
Podemos encontrar todos los subconjuntos de tamaño K , luego ordenar los subconjuntos y encontrar el valor de cada subconjunto y multiplicarlo para obtener la respuesta final.
Como puede haber 2 N subconjuntos, este enfoque no será muy eficiente para un gran valor de N.
Enfoque eficiente:
- La idea no es crear todos los subconjuntos para encontrar la respuesta, sino calcular la cuenta de cada elemento en todos los subconjuntos. Si encontramos el recuento de cada elemento en todos los subconjuntos, la respuesta será
![\text{Final answer} = ((arr[1]^{(\text{count of arr[1]})}) * ((arr[2]^{(\text{count of arr[2]})})* ..... *((arr[N]^{(\text{count of arr[N]})})](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-ee16b8778dc46204021d3c13233d0ba9_l3.png "Rendered by QuickLaTeX.com")
- Para encontrar el conteo de arr[i], tenemos que encontrar el número total de los diferentes subconjuntos que se pueden formar colocando arr[i] en cada índice posible que divide a K por completo.
- El número de conjuntos formados al colocar arr[i] en el índice j ( j divide a K por completo) será:
( Nº total de elementos menores que arr[i] ) C j-1 * ( Nº total de elementos mayores que arr[i] ) C k-j
- Como la cuenta de cualquier elemento puede ser muy grande, entonces para encontrar ( arr[i] ( cuenta de arr[i]) ) % ( 10 9 + 7 ) tenemos que usar el pequeño teorema de Fermat que es
{ a (p – 1) mod p = 1 } => { ( a x ) % p = ( a ( x % p-1 ) ) % p }.
Entonces, usando el pequeño teorema de Fermat
( arr[i] (recuento de arr[i] ) ) % ( 10 9 + 7 ) => ( arr[i] (recuento de arr[i] % 109 + 6 ) ) % ( 10 9 + 7 ).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
int p = 1000000007;
// Iterative Function to calculate
// (x^y)%p in O(log y)
long long int power(long long int x,
long long int y,
long long int p)
{
long long int res = 1;
x = x % p;
while (y > 0) {
// If y is odd, multiply
// x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Iterative Function to calculate
// (nCr)%p and save in f[n][r]
void nCr(long long int n, long long int p,
int f[][100], int m)
{
for (long long int i = 0; i <= n; i++) {
for (long long int j = 0; j <= m; j++) {
// If j>i then C(i, j) = 0
if (j > i) {
f[i][j] = 0;
}
// If iis equal to j then
// C(i, j) = 1
else if (j == 0 || j == i) {
f[i][j] = 1;
}
else {
f[i][j] = (f[i - 1][j]
+ f[i - 1][j - 1])
% p;
}
}
}
}
// Function calculate the Final answer
void ProductOfSubsets(int arr[], int n,
int m)
{
int f[n + 1][100];
nCr(n, p - 1, f, m);
sort(arr, arr + n);
// Initialize ans
long long int ans = 1;
for (long long int i = 0; i < n; i++) {
// x is count of occurence of arr[i]
// in different set such that index
// of arr[i] in those sets divides
// K completely.
long long int x = 0;
for (long long int j = 1; j <= m; j++) {
// Finding the count of arr[i] by
// placing it at index which
// divides K completely
if (m % j == 0) {
// By Fermat's theorem
x = (x
+ (f[n - i - 1][m - j]
* f[i][j - 1])
% (p - 1))
% (p - 1);
}
}
ans
= ((ans * power(arr[i], x, p)) % p);
}
cout << ans << endl;
}
// Driver code
int main()
{
int arr[] = { 4, 5, 7, 9, 3 };
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
ProductOfSubsets(arr, N, K);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
static int p = 1000000007;
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
int res = 1;
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Iterative Function to calculate
// (nCr)%p and save in f[n][r]
static void nCr(int n, int p,
int f[][], int m)
{
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
// If j>i then C(i, j) = 0
if (j > i)
{
f[i][j] = 0;
}
// If iis equal to j then
// C(i, j) = 1
else if (j == 0 || j == i)
{
f[i][j] = 1;
}
else
{
f[i][j] = (f[i - 1][j] +
f[i - 1][j - 1]) % p;
}
}
}
}
// Function calculate the Final answer
static void ProductOfSubsets(int arr[], int n,
int m)
{
int [][]f = new int[n + 1][100];
nCr(n, p - 1, f, m);
Arrays.sort(arr);
// Initialize ans
long ans = 1;
for(int i = 0; i < n; i++)
{
// x is count of occurence of arr[i]
// in different set such that index
// of arr[i] in those sets divides
// K completely.
int x = 0;
for(int j = 1; j <= m; j++)
{
// Finding the count of arr[i] by
// placing it at index which
// divides K completely
if (m % j == 0)
{
// By Fermat's theorem
x = (x + (f[n - i - 1][m - j] *
f[i][j - 1]) %
(p - 1)) %
(p - 1);
}
}
ans = ((ans * power(arr[i], x, p)) % p);
}
System.out.print(ans + "\n");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 5, 7, 9, 3 };
int K = 4;
int N = arr.length;
ProductOfSubsets(arr, N, K);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach p = 1000000007 # Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y, p): res = 1 x = x % p while (y > 0): # If y is odd, multiply # x with result if (y & 1): res = (res * x) % p # y must be even now y = y >> 1 x = (x * x) % p return res # Iterative Function to calculate # (nCr)%p and save in f[n][r] def nCr(n, p, f, m): for i in range(n + 1): for j in range(m + 1): # If j>i then C(i, j) = 0 if (j > i): f[i][j] = 0 # If i is equal to j then # C(i, j) = 1 elif(j == 0 or j == i): f[i][j] = 1 else: f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % p # Function calculate the Final answer def ProductOfSubsets(arr, n, m): f = [[0 for i in range(100)] for j in range(n + 1)] nCr(n, p - 1, f, m) arr.sort(reverse = False) # Initialize ans ans = 1 for i in range(n): # x is count of occurence of arr[i] # in different set such that index # of arr[i] in those sets divides # K completely. x = 0 for j in range(1, m + 1, 1): # Finding the count of arr[i] by # placing it at index which # divides K completely if (m % j == 0): # By Fermat's theorem x = ((x + (f[n - i - 1][m - j] * f[i][j - 1]) % (p - 1)) % (p - 1)) ans = ((ans * power(arr[i], x, p)) % p) print(ans) # Driver code if __name__ == '__main__': arr = [ 4, 5, 7, 9, 3 ] K = 4 N = len(arr); ProductOfSubsets(arr, N, K) # This code is contributed by samarth
C#
// C# implementation of the above approach
using System;
class GFG{
static int p = 1000000007;
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
int res = 1;
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Iterative Function to calculate
// (nCr)%p and save in f[n,r]
static void nCr(int n, int p,
int [,]f, int m)
{
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
// If j>i then C(i, j) = 0
if (j > i)
{
f[i, j] = 0;
}
// If iis equal to j then
// C(i, j) = 1
else if (j == 0 || j == i)
{
f[i, j] = 1;
}
else
{
f[i, j] = (f[i - 1, j] +
f[i - 1, j - 1]) % p;
}
}
}
}
// Function calculate the Final answer
static void ProductOfSubsets(int []arr, int n,
int m)
{
int [,]f = new int[n + 1, 100];
nCr(n, p - 1, f, m);
Array.Sort(arr);
// Initialize ans
long ans = 1;
for(int i = 0; i < n; i++)
{
// x is count of occurence of arr[i]
// in different set such that index
// of arr[i] in those sets divides
// K completely.
int x = 0;
for(int j = 1; j <= m; j++)
{
// Finding the count of arr[i] by
// placing it at index which
// divides K completely
if (m % j == 0)
{
// By Fermat's theorem
x = (x + (f[n - i - 1, m - j] *
f[i, j - 1]) %
(p - 1)) %
(p - 1);
}
}
ans = ((ans * power(arr[i], x, p)) % p);
}
Console.Write(ans + "\n");
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 4, 5, 7, 9, 3 };
int K = 4;
int N = arr.Length;
ProductOfSubsets(arr, N, K);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation
// for the above approach
let p = 1000000007;
// Iterative Function to calculate
// (x^y)%p in O(log y)
function power(x, y, p)
{
let res = 1;
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Iterative Function to calculate
// (nCr)%p and save in f[n][r]
function nCr(n, p, f, m)
{
for(let i = 0; i <= n; i++)
{
for(let j = 0; j <= m; j++)
{
// If j>i then C(i, j) = 0
if (j > i)
{
f[i][j] = 0;
}
// If iis equal to j then
// C(i, j) = 1
else if (j == 0 || j == i)
{
f[i][j] = 1;
}
else
{
f[i][j] = (f[i - 1][j] +
f[i - 1][j - 1]) % p;
}
}
}
}
// Function calculate the Final answer
function ProductOfSubsets(arr, n, m)
{
let f = new Array(n+1);
for (var i = 0; i < f.length; i++) {
f[i] = new Array(2);
}
nCr(n, p - 1, f, m);
arr.sort();
// Initialize ans
let ans = 1;
for(let i = 0; i < n; i++)
{
// x is count of occurence of arr[i]
// in different set such that index
// of arr[i] in those sets divides
// K completely.
let x = 0;
for(let j = 1; j <= m; j++)
{
// Finding the count of arr[i] by
// placing it at index which
// divides K completely
if (m % j == 0)
{
// By Fermat's theorem
x = (x + (f[n - i - 1][m - j] *
f[i][j - 1]) %
(p - 1)) %
(p - 1);
}
}
ans = ((ans * power(arr[i], x, p)) % p);
}
document.write(ans + "<br/>");
}
// Driver Code
let arr = [ 4, 5, 7, 9, 3 ];
let K = 4;
let N = arr.length;
ProductOfSubsets(arr, N, K);
</script>
Producción:
808556639
Tiempo Complejidad: (N * K)
Espacio Auxiliar: O(N * 100)