数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中大小为 K 的所有子序列的乘积，除了最小和最大元素
给定一个数组 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) 次它将作为该子序列的最小元素出现。
因此，我们可以说这是一种更有效的方法，因为第 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
更新于: 2019-12-23
157 次查看
广告