Giả sử chúng ta có một mảng A gồm các số nguyên, coi tất cả các dãy con không rỗng của A. Với bất kỳ dãy nào S, coi độ rộng của S là hiệu giữa phần tử lớn nhất và nhỏ nhất của S. Chúng ta phải tìm tổng các độ rộng của tất cả các dãy con của A. Câu trả lời có thể rất lớn, vì vậy hãy trả về mô-đun câu trả lời 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là [3,1,2], thì đầu ra sẽ là 6, điều này là do các dãy con giống như [1], [2], [3], [2,1], [2, 3], [1,3], [2,1,3] và chiều rộng là 0, 0, 0, 1, 1, 2, 2, vì vậy tổng các giá trị chiều rộng là 6.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm add (), điều này sẽ lấy a, b,
-
return ((a mod m) + (b mod m)) mod m
-
Xác định một hàm sub (), điều này sẽ lấy a, b,
-
return (((a mod m) - (b mod m)) + m) mod m
-
Xác định một hàm mul (), điều này sẽ nhận a, b,
-
return ((a mod m) * (b mod m)) mod m
-
Từ phương thức chính, thực hiện như sau -
-
sắp xếp mảng a
-
ans:=0
-
n:=kích thước của một
-
rcnt:=1
-
để khởi tạo i:=0, khi i
-
x =mul (a [i], sub (rcnt, 1))
-
y =mul (a [n-1-i], sub (rcnt, 1))
-
ans =add (ans, sub (x, y))
-
rcnt =rcnt * 2
-
rcnt:=rcnt mod m
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % m) + (b % m) ) % m;
}
lli sub(lli a, lli b){
return ( ( (a % m) - (b % m) ) + m ) % m;
}
lli mul(lli a, lli b){
return ( (a % m) * (b % m) ) % m;
}
int sumSubseqWidths(vector<int>& a) {
sort(a.begin(), a.end());
int ans = 0;
int n = a.size();
lli rcnt = 1;
for(int i = 0 ; i < n; i++){
ans = add (ans, sub(mul(a[i] , sub(rcnt , 1)), mul(a[n-1-i], sub(rcnt,1))));
rcnt <<=1;
rcnt %= m;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {3,1,2};
cout << (ob.sumSubseqWidths(v));
} Đầu vào
{3,1,2} Đầu ra
6