C++の最小要素と最大要素を除くサイズKのすべてのサブシーケンスの積

n個の整数とサイズを定義するための整数kを含む配列arr[n]が与えられます。タスクは、最小要素と最大要素を除く、サイズ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

上記の問題を解決するために使用しているアプローチ −

解決策を達成する方法はたくさんあります。可能なすべてのサブシーケンスを1つずつ生成し、セットの最大値と最小値を除くすべての要素を生成できる1つのアプローチがあります。このアプローチは簡単に実現できますが、非常に複雑であり、非効率的です。

効率的なアプローチもあります。このアプローチでは、最初に配列をソートし、考慮されるサブセットまたは後続のサブセットを無視します。

次に、各要素の発生数を1つずつカウントします。

いくつかの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のmodで回答を出力します。

アルゴリズム

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