C++에서 하위 시퀀스 너비의 합

<시간/>

정수 배열 A가 있다고 가정하고 A의 비어 있지 않은 모든 하위 시퀀스를 고려합니다. 시퀀스 S에 대해 S의 너비를 S의 최대 요소와 최소 요소 간의 차이로 간주합니다. 너비의 합을 찾아야 합니다. A의 모든 하위 시퀀스. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 [3,1,2]와 같으면 출력이 6이 됩니다. 이는 하위 시퀀스가 [1], [2], [3], [2,1], [2, 3], [1,3], [2,1,3]이고 너비는 0, 0, 0, 1, 1, 2, 2이므로 너비 값의 합은 6입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
함수 sub()를 정의하면, b,
return (((a mod m) - (b mod m)) + m) mod m
mul() 함수를 정의하면, b,
return ((a mod m) * (b mod m)) mod m
기본 방법에서 다음을 수행하십시오 -
배열 정렬 a
답변 :=0
n :=a
의 크기
rcnt :=1
initialize i :=0의 경우, 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 모드 m
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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));
}

입력

{3,1,2}