배열 arr[n]이 주어지면 n개의 정수와 크기를 정의하기 위한 정수 k를 포함합니다. 작업은 최소 및 최대 요소를 제외한 크기 k의 모든 부분 수열의 곱을 인쇄하는 것입니다.
4개의 요소 {1, 2, 3, 4} 및 k가 2인 세트가 있다고 가정해 보겠습니다. 4}, {1, 3}, {2, 4}
따라서 최대 요소 4와 최소 요소 1을 제외하고 나머지 요소는 -
2, 3, 3, 3, 2, 그 곱은 -
2 * 3 * 3 * 3 * 2 =108
마찬가지로 문제를 해결해야 합니다.
예시
Input: arr[] = {3, 4, 1, 7}, k = 3
Output: 144
Explanation: subset will be, {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7}
Eliminating maximum value 7 and minimum 1 we will get:
{3, 4}, {4}, {3}, {3, 4}, so multiplying these will give us:
3 * 4 * 4 * 3 = 144
Input: arr[] = {1, 2, 3, 4}, k = 3
Output: 36 위의 문제를 해결하기 위해 사용하는 접근 방식 -
솔루션을 달성하는 방법에는 여러 가지가 있을 수 있습니다. 가능한 모든 부분 수열을 하나씩 생성하고 집합의 최대값과 최소값을 제외한 모든 요소를 곱할 수 있는 한 가지 접근 방식이 있습니다. 이 접근 방식은 달성하기 쉽지만 복잡성이 매우 높고 접근 방식이 비효율적이지만
우리는 효율적인 접근 방식도 가지고 있습니다. 이 접근 방식에서는 먼저 배열을 정렬하고, 하위 집합 또는 후속 항목을 고려하는지 여부를 무시합니다.
그런 다음 각 요소의 발생 횟수를 하나씩 계산합니다.
숫자가 발생할 수 있습니다 C(k-1) (n-1) C(k-1) (i) 번 우리가 발생할 것입니다 최대 요소 C(k-1) (n-i-1) 번 발생할 것입니다 해당 하위 시퀀스의 최소 요소입니다.
따라서 i번째 요소가 발생하므로 이것이 더 효율적인 접근 방식이라고 말할 수 있습니다. -
C(k-1) (n-1)- C(k-1) (i)- C(k-1) (n-i-1) 배.
이제 먼저 arr[i]의 각 요소에 대해 x를 풀어서 페르마의 작은 정리를 사용할 수 있도록 답을 계산하기가 정말 어려울 수 있습니다.
참고 −답이 정말 클 수 있으므로 109+7 모드로 답을 인쇄합니다.
알고리즘
Start
Step 1-> Declare function to calculate the pairs combination
void pairs(int a, int b)
Declare int i, j
Loop For i = 0 and i <= a and i++
Loop For j = 0 and j <= min(i, b) and j++
IF (j == 0 || j == i)
Set c[i][j] = 1
End
Else
Set c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val
End
End
End
Step 2-> declare function for power
LL power(LL x, unsigned LL y)
Declare unsigned LL temp = 1
Set x = x % val
Loop While (y > 0)
IF(y & 1)
Set temp = (temp * x) % val
End
Set y = y >> 1
Set x = (x * x) % val
End
return temp % val
Step 3-> Declare function to calculate product of all subsequences
unsigned LL product(LL arr[], int size, int k)
Declare and set unsigned LL temp = 1
Call function to sort an array as sort(arr, arr + size)
Declare and set as LL pow = c[size - 1][k - 1]
Loop For i = 0 and i < size and i++
Declare and set LL pow_l = c[i][k - 1]
Declare and set LL pow_f = c[size - i - 1][k - 1]
Declare and set LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val
Declare and set unsigned LL mul = power(arr[i], pow_e) % val
Set temp = ((temp % val) * (mul % val)) % val
End
return temp % val
Step 4-> In main()
Call pairs(100, 100)
Declare and set LL arr[] = { 3, 4, 1, 7 }
Calculate size as int size = sizeof(arr) / sizeof arr[0]
Declare and set int k = 3
Declare and set unsigned LL temp = product(arr, size, k)
Print temp
Stop 예시
#include <bits/stdc++.h>
using namespace std;
#define val 1000000007
#define LL long long
#define max 101
LL c[max - 1][max - 1];
LL power(LL x, unsigned LL y) {
unsigned LL temp = 1;
x = x % val;
while (y > 0) {
if (y & 1) {
temp = (temp * x) % val;
}
y = y >> 1;
x = (x * x) % val;
}
return temp % val;
}
void pairs(int a, int b) {
int i, j;
for (i = 0; i <= a; i++) {
for (j = 0; j <= min(i, b); j++) {
if (j == 0 || j == i)
c[i][j] = 1;
else
c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val;
}
}
}
//function to calculate product of all subsequences
unsigned LL product(LL arr[], int size, int k) {
unsigned LL temp = 1;
//sorting array
sort(arr, arr + size);
LL pow = c[size - 1][k - 1];
for (int i = 0; i < size; i++) {
LL pow_l = c[i][k - 1];
LL pow_f = c[size - i - 1][k - 1];
LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val;
unsigned LL mul = power(arr[i], pow_e) % val;
temp = ((temp % val) * (mul % val)) % val;
}
return temp % val;
}
int main() {
// sum of all the pairs
pairs(100, 100);
LL arr[] = { 3, 4, 1, 7 };
int size = sizeof(arr) / sizeof arr[0];
int k = 3;
unsigned LL temp = product(arr, size, k);
cout<<"product of all subsequences of size k except minimum and maximum element is :"<<temp << endl;
return 0;
} 출력
product of all subsequences of size k except minimum and maximum element is :144