ผลคูณของทุก subsequence ขนาด K ยกเว้นค่าต่ำสุดและสูงสุดใน C++

โจทย์

กำหนดอาเรย์ arr[n] ที่มีจำนวนเต็ม n ตัว และจำนวนเต็ม k สำหรับกำหนดขนาด งานคือพิมพ์ผลคูณของทุก subsequence ขนาด k ยกเว้นองค์ประกอบที่มีค่าต่ำสุดและสูงสุด

สมมติเรามีชุด 4 องค์ประกอบ {1, 2, 3, 4} และ k เป็น 2 ดังนั้น subset จะเป็น - {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 จะเป็น, {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7} กำจัดค่าสูงสุด 7 และต่ำสุด 1 จะได้: {3, 4}, {4}, {3}, {3, 4} คูณกันจะได้: 3 * 4 * 4 * 3 = 144
Input: arr[] = {1, 2, 3, 4}, k = 3 Output: 36

แนวทางแก้ปัญหา

สามารถมีหลายวิธีในการแก้ปัญหา วิธีหนึ่งคือสร้าง subsequence ทั้งหมดทีละอัน และคูณองค์ประกอบทั้งหมดยกเว้นค่าสูงสุดและต่ำสุดของชุด แม้วิธีนี้จะง่ายแต่มีความซับซ้อนสูงมากและไม่มีประสิทธิภาพ

เรามีวิธีที่มีประสิทธิภาพมากกว่า ในวิธีนี้เราจะเรียงอาเรย์ก่อน โดยไม่สนใจ subset หรือ subsequence ว่าจะพิจารณาหรือไม่

จากนั้นเราจะนับจำนวนครั้งที่แต่ละองค์ประกอบเกิดขึ้นทีละตัว

ตัวเลขสามารถเกิดขึ้น C(k-1) (n-1) subsequences ซึ่งในนั้น C(k-1) (i) ครั้งจะเป็นค่าสูงสุด C(k-1) (n-i-1) ครั้งจะเป็นค่าต่ำสุดของ subsequence นั้น

ดังนั้น เราสามารถระบุได้ว่า นี่คือวิธีที่มีประสิทธิภาพมากกว่า เนื่องจากองค์ประกอบที่ i จะเกิดขึ้น -

C(k-1) (n-1) - C(k-1) (i) - C(k-1) (n-i-1) ครั้ง

ตอนนี้ เราจะแก้ x สำหรับแต่ละองค์ประกอบใน arr[i] คำตอบอาจคำนวณได้ยาก ดังนั้นเราสามารถใช้ทฤษฎีบทเล็กของเฟอร์มาได้

หมายเหตุ - เนื่องจากคำตอบอาจใหญ่มาก เราจะพิมพ์คำตอบในโมดของ 10^9+7

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ประกาศฟังก์ชันคำนวณการจับคู่
  void pairs(int a, int b)
  ประกาศ int i, j
  วนลูป For i = 0 ถึง a และ i++
    วนลูป For j = 0 ถึง min(i, b) และ j++
      ถ้า (j == 0 || j == i)
        ตั้งค่า c[i][j] = 1
      จบถ้า
      มิฉะนั้น
        ตั้งค่า c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val
      จบมิฉะนั้น
    จบวน
  จบวน
ขั้นตอน 2 → ประกาศฟังก์ชันยกกำลัง
  LL power(LL x, unsigned LL y)
  ประกาศ unsigned LL temp = 1
  ตั้งค่า x = x % val
  วนลูป While (y > 0)
    ถ้า (y & 1)
      ตั้งค่า temp = (temp * x) % val
    จบถ้า
    ตั้งค่า y = y >> 1
    ตั้งค่า x = (x * x) % val
  จบวน
  คืนค่า temp % val
ขั้นตอน 3 → ประกาศฟังก์ชันคำนวณผลคูณของทุก subsequences
  unsigned LL product(LL arr[], int size, int k)
  ประกาศและตั้งค่า unsigned LL temp = 1
  เรียกฟังก์ชันเรียงอาเรย์ sort(arr, arr + size)
  ประกาศและตั้งค่า LL pow = c[size - 1][k - 1]
  วนลูป For i = 0 ถึง 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
  จบวน
  คืนค่า temp % val
ขั้นตอน 4 → ใน main()
  เรียก 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)
  พิมพ์ temp
หยุด

ตัวอย่างโค้ด C++

#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;
    }
  }
}
// ฟังก์ชันคำนวณผลคูณของทุก subsequences
unsigned LL product(LL arr[], int size, int k) {
  unsigned LL temp = 1;
  // เรียงอาเรย์
  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() {
  // ผลรวมของทุกคู่
  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