Dada una array arr[] de N enteros distintos y un entero positivo M , la tarea es encontrar el producto de todos los elementos en los índices que son los factores de M para todas las posibles subsecuencias ordenadas de longitud M de la array dada arr [] .
Nota: El producto puede ser muy grande, tome módulo a 10 9 + 7 .
Ejemplos:
Entrada: arr[] = {4, 7, 5, 9, 3}, M = 4
Salida: 808556639
Explicación:
Hay cinco conjuntos posibles. Ellos son:
{4, 7, 5, 9}. En el orden ordenado, este conjunto se convierte en {4, 5, 7, 9}. En este conjunto, el índice 1, 2 y 4 divide a M por completo. Por lo tanto, arr[1] * arr[2] * arr[4] = 4 * 5 * 9 = 180.
De manera similar, los cuatro conjuntos restantes junto con sus productos son:
{4, 7, 9, 3} -> 108
{ 4, 5, 9, 3} -> 108
{4, 7, 5, 3} -> 84
{7, 5, 9, 3} -> 135
El valor total = ((180 * 108 * 108 * 84 * 135 ) % (10^9+7)) = 808556639Entrada: arr[] = {7, 8, 9}, M = 2
Salida: 254016
Enfoque: Dado que no es posible encontrar todos los conjuntos, la idea es contar el número total de veces que cada elemento aparece en la posición requerida. Si se encuentra el conteo, entonces:
producto = (arr[1] cuenta de arr[1] ) * (arr[2] cuenta de arr[2] )* ….. *(arr[N] cuenta de arr[N] )
- Para encontrar la cuenta del arr[i], tenemos que encontrar el número total de los diferentes conjuntos que se pueden formar colocando arr[i] en cada índice posible (que divide a M por completo).
- Por lo tanto, el número de conjuntos formados al colocar arr[i] en el índice jth (j divide m completamente) será:
(Número de elementos menor que arr[i]) C j-1 * (Número de elementos mayor que arr[i]) C M-j
- Como la cuenta de cualquier elemento puede ser muy grande, para encontrar (arr[i] cuenta de arr[i] ) % (10 9 + 7) , se usa el pequeño teorema de Fermat .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the product of
// all the combinations of M elements
// from an array whose index in the
// sorted order divides M completely
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 4;
// Iterative Function to calculate
// (x^y)%p in O(log y)
long long int power(lli x, lli y, lli p)
{
lli 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]
// C(n, r)%p = [ C(n-1, r-1)%p + C(n-1, r)%p ] % p
// and C(n, 0) = C(n, n) = 1
void nCr(lli n, lli p, lli f[][m + 1])
{
for (lli i = 0; i <= n; i++) {
for (lli j = 0; j <= m; j++) {
// 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
else if (j == 0 || j == i)
f[i][j] = 1;
// C(i, j) = ( C(i-1, j) + C(i-1, j-1))%p
else
f[i][j] = (f[i - 1][j]
+ f[i - 1][j - 1])
% p;
}
}
}
void operations(lli arr[], lli n, lli f[][m + 1])
{
lli p = 1000000007;
nCr(n, p - 1, f);
sort(arr, arr + n);
// Initialize the answer
lli ans = 1;
for (lli i = 0; i < n; i++) {
// For every element arr[i],
// x is count of occurrence
// of arr[i] in different set
// such that index of arr[i]
// in those sets divides m completely.
long long int x = 0;
for (lli j = 1; j <= m; j++) {
// Finding the count of arr[i]
// by placing it at the index
// which divides m completely
if (m % j == 0)
// Using fermat's little theorem
x = (x
+ (f[n - i - 1][m - j]
* f[i][j - 1])
% (p - 1))
% (p - 1);
}
// Multiplying with the count
ans = ((ans * power(arr[i],
x, p))
% p);
}
cout << ans << endl;
}
// Driver code
int main()
{
lli arr[] = { 4, 5, 7, 9, 3 };
lli n = sizeof(arr) / sizeof(arr[0]);
lli f[n + 1][m + 1];
operations(arr, n, f);
}
Java
// Java program to find the product of
// all the combinations of M elements
// from an array whose index in the
// sorted order divides M completely
import java.util.*;
class GFG{
static int m = 4;
// Iterative Function to calculate
// (x^y)%p in O(log y)
static long power(long x, long y, long p)
{
long 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]
// C(n, r)%p = [ C(n-1, r-1)%p + C(n-1, r)%p ] % p
// and C(n, 0) = C(n, n) = 1
static void nCr(int n, long p, int f[][])
{
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 i is equal to j
// then C(i, j) = 1
else if (j == 0 || j == i)
f[i][j] = 1;
// C(i, j) = ( C(i-1, j) + C(i-1, j-1))%p
else
f[i][j] = (f[i - 1][j] +
f[i - 1][j - 1]) % (int)p;
}
}
}
static void operations(int arr[], int n, int f[][])
{
long p = 1000000007;
nCr(n, p - 1, f);
Arrays.sort(arr);
// Initialize the answer
long ans = 1;
for(int i = 0; i < n; i++)
{
// For every element arr[i],
// x is count of occurrence
// of arr[i] in different set
// such that index of arr[i]
// in those sets divides m
// completely.
long x = 0;
for(int j = 1; j <= m; j++)
{
// Finding the count of arr[i]
// by placing it at the index
// which divides m completely
if (m % j == 0)
// Using fermat's little theorem
x = (x + (f[n - i - 1][m - j] *
f[i][j - 1]) %
(p - 1)) %
(p - 1);
}
// Multiplying with the count
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 n = arr.length;
int [][]f = new int[n + 1][m + 1];
operations(arr, n, f);
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program to find the product of # all the combinations of M elements # from an array whose index in the # sorted order divides M completely m = 4 # 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] # C(n, r)%p = [ C(n-1, r-1)%p + # C(n-1, r)%p ] % p # and C(n, 0) = C(n, n) = 1 def nCr(n, p, f): for i in range (n): 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 # C(i, j) = ( C(i-1, j) + # C(i-1, j-1))%p else: f[i][j] = ((f[i - 1][j] + f[i - 1][j - 1]) % p) def operations(arr, n, f): p = 1000000007 nCr(n, p - 1, f) arr.sort() # Initialize the answer ans = 1 for i in range (n): # For every element arr[i], # x is count of occurrence # of arr[i] in different set # such that index of arr[i] # in those sets divides m completely. x = 0 for j in range (1, m + 1): # Finding the count of arr[i] # by placing it at the index # which divides m completely if (m % j == 0): # Using fermat's little theorem x = ((x + (f[n - i - 1][m - j] * f[i][j - 1]) % (p - 1)) % (p - 1)) # Multiplying with the count ans = ((ans * power(arr[i], x, p)) % p) print (ans) # Driver code if __name__ == "__main__": arr = [4, 5, 7, 9, 3] n = len(arr) f = [[0 for x in range (m + 1)] for y in range (n + 1)] operations(arr, n, f) # This code is contributed by Chitranayal
C#
// C# program to find the product of
// all the combinations of M elements
// from an array whose index in the
// sorted order divides M completely
using System;
class GFG{
static int m = 4;
// Iterative Function to calculate
// (x^y)%p in O(log y)
static long power(long x, long y, long p)
{
long 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]
// C(n, r)%p = [ C(n-1, r-1)%p + C(n-1, r)%p ] % p
// and C(n, 0) = C(n, n) = 1
static void nCr(int n, long p, int [,]f)
{
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 i is equal to j
// then C(i, j) = 1
else if (j == 0 || j == i)
f[i, j] = 1;
// C(i, j) = ( C(i-1, j) + C(i-1, j-1))%p
else
f[i, j] = (f[i - 1, j] +
f[i - 1, j - 1]) % (int)p;
}
}
}
static void operations(int []arr, int n, int [,]f)
{
long p = 1000000007;
nCr(n, p - 1, f);
Array.Sort(arr);
// Initialize the answer
long ans = 1;
for(int i = 0; i < n; i++)
{
// For every element arr[i],
// x is count of occurrence
// of arr[i] in different set
// such that index of arr[i]
// in those sets divides m
// completely.
long x = 0;
for(int j = 1; j <= m; j++)
{
// Finding the count of arr[i]
// by placing it at the index
// which divides m completely
if (m % j == 0)
// Using fermat's little theorem
x = (x + (f[n - i - 1, m - j] *
f[i, j - 1]) %
(p - 1)) %
(p - 1);
}
// Multiplying with the count
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 n = arr.Length;
int [,]f = new int[n + 1, m + 1];
operations(arr, n, f);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program to find the product of
// all the combinations of M elements
// from an array whose index in the
// sorted order divides M completely
let m = 4;
// 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]
// C(n, r)%p = [ C(n-1, r-1)%p + C(n-1, r)%p ] % p
// and C(n, 0) = C(n, n) = 1
function nCr(n, p, f)
{
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 i is equal to j
// then C(i, j) = 1
else if (j == 0 || j == i)
f[i][j] = 1;
// C(i, j) = ( C(i-1, j) + C(i-1, j-1))%p
else
f[i][j] = (f[i - 1][j] +
f[i - 1][j - 1]) % p;
}
}
}
function operations(arr, n, f)
{
let p = 1000000007;
nCr(n, p - 1, f);
arr.sort();
// Initialize the answer
let ans = 1;
for(let i = 0; i < n; i++)
{
// For every element arr[i],
// x is count of occurrence
// of arr[i] in different set
// such that index of arr[i]
// in those sets divides m
// completely.
let x = 0;
for(let j = 1; j <= m; j++)
{
// Finding the count of arr[i]
// by placing it at the index
// which divides m completely
if (m % j == 0)
// Using fermat's little theorem
x = (x + (f[n - i - 1][m - j] *
f[i][j - 1]) %
(p - 1)) %
(p - 1);
}
// Multiplying with the count
ans = ((ans * power(arr[i], x, p)) % p);
}
document.write(ans + "\n");
}
// Driver Code
let arr = [ 4, 5, 7, 9, 3 ];
let n = arr.length;
let f = new Array(n + 1);
for(var i = 0; i < f.length; i++)
{
f[i] = new Array(2);
}
operations(arr, n, f);
// This code is contributed by target_2
</script>
Producción:
808556639
Complejidad de tiempo: O(N * M) donde N es la longitud de la array y M la proporciona el usuario.
Espacio Auxiliar: O(N * M)