একটি অ্যারে arr[n] দেওয়া আছে যাতে n সংখ্যক ইন্টিজার আছে এবং সাইজ নির্ধারণের জন্য একটি ইন্টিজার k। কাজ হলো সাইজ k-এর সব সাবসিকোয়েন্সের গুণফল বের করা, তবে প্রতিটি সাবসিকোয়েন্স থেকে ন্যূনতম এবং সর্বোচ্চ এলিমেন্ট বাদ দিয়ে।
মনে করি, ৪টি এলিমেন্টের সেট {1, 2, 3, 4} এবং k = 2। এর সাবসেটগুলো হবে: {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}
সর্বোচ্চ এলিমেন্ট ৪ এবং ন্যূনতম ১ বাদ দিয়ে বাকি এলিমেন্টগুলো: ২, ৩, ৩, ৩, ২, যাদের গুণফল: ২ * ৩ * ৩ * ৩ * ২ = ১০৮
এভাবেই সমস্যাটি সমাধান করতে হবে।
উদাহরণ
ইনপুট: arr[] = {3, 4, 1, 7}, k = 3 আউটপুট: 144 ব্যাখ্যা: সাবসেট হবে, {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7} সর্বোচ্চ ৭ এবং ন্যূনতম ১ বাদ দিলে পাব: {3, 4}, {4}, {3}, {3, 4}, গুণফল: 3 * 4 * 4 * 3 = 144
ইনপুট: arr[] = {1, 2, 3, 4}, k = 3 আউটপুট: 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 বের করব। উত্তর বড় হতে পারায় ফার্মেটস লিটল থিওরেম ব্যবহার করা হয়।
দ্রষ্টব্য - উত্তর খুব বড় হতে পারে, তাই ১০⁹+৭ মডুলোতে প্রিন্ট করা হবে।
অ্যালগরিদম
শুরু
ধাপ ১ -> কোম্বিনেশন গণনার ফাংশন ঘোষণা
void pairs(int a, int b)
int i, j ঘোষণা
লুপ i = 0 থেকে i <= a এবং i++
লুপ j = 0 থেকে j <= 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 সেট
শেষ
শেষ
শেষ
ধাপ ২ -> পাওয়ার ফাংশন ঘোষণা
LL power(LL x, unsigned LL y)
unsigned LL temp = 1 ঘোষণা
x = x % val সেট
লুপ যতক্ষণ (y > 0)
যদি (y & 1)
temp = (temp * x) % val সেট
শেষ
y = y >> 1 সেট
x = (x * x) % val সেট
শেষ
return temp % val
ধাপ ৩ -> সাবসিকোয়েন্সের গুণফল গণনার ফাংশন ঘোষণা
unsigned LL product(LL arr[], int size, int k)
unsigned LL temp = 1 ঘোষণা এবং সেট
অ্যারে সর্ট: sort(arr, arr + size)
LL pow = c[size - 1][k - 1] ঘোষণা এবং সেট
লুপ 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
ধাপ ৪ -> main()-এ
pairs(100, 100) কল
LL arr[] = { 3, 4, 1, 7 } ঘোষণা এবং সেট
size = sizeof(arr) / sizeof arr[0] গণনা
int k = 3 ঘোষণা এবং সেট
unsigned LL temp = product(arr, size, k) ঘোষণা এবং সেট
temp প্রিন্ট
শেষ
উদাহরণ
#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;
}
}
}
// সাবসিকোয়েন্সের গুণফল গণনা
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
