กำหนดอาร์เรย์ arr[n] ซึ่งประกอบด้วยจำนวน n จำนวนเต็มและจำนวนเต็ม k สำหรับกำหนดขนาด งานคือการพิมพ์ผลิตภัณฑ์ของลำดับย่อยทั้งหมดของขนาด k ยกเว้นองค์ประกอบต่ำสุดและสูงสุด
สมมติว่าเรามีชุดขององค์ประกอบ 4 รายการ {1, 2, 3, 4} และ k เป็น 2 ดังนั้นชุดย่อยจะเป็น −{1, 2}, {2, 3}, {3, 4}, {1, 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) ครั้งที่จะเกิดขึ้น เป็นองค์ประกอบขั้นต่ำของลำดับนั้น
ดังนั้น เราสามารถระบุได้ว่าวิธีนี้เป็นวิธีที่มีประสิทธิภาพมากกว่าเนื่องจากองค์ประกอบ ith จะเกิดขึ้น -
C(k-1) (n-1)- C(k-1) (i)- C(k-1) (n-i-1) ครั้ง
ขั้นแรกเราจะแก้ x สำหรับแต่ละองค์ประกอบใน arr[i] ดังนั้นคำตอบของมันจึงเป็นเรื่องยากที่จะคำนวณ เราจึงสามารถใช้ทฤษฎีบทน้อยของ Fermat ได้
หมายเหตุ −เนื่องจากคำตอบอาจมีขนาดใหญ่มาก ดังนั้นเราจะพิมพ์คำตอบใน mod 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
