ผลรวมของความกว้างที่ตามมาใน C++

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็ม ให้พิจารณาลำดับย่อยที่ไม่ว่างทั้งหมดของ A สำหรับลำดับ S ใดๆ ให้พิจารณาความกว้างของ S คือผลต่างระหว่างองค์ประกอบสูงสุดและต่ำสุดของ S เราต้องหาผลรวมของความกว้างของ ลำดับย่อยทั้งหมดของ A คำตอบอาจมีขนาดใหญ่มาก ดังนั้นให้ส่งคืน modulo 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() ซึ่งจะใช้ a, b,

• กลับ ((a mod m) + (b mod m)) mod m

• กำหนดฟังก์ชั่นย่อย () สิ่งนี้จะใช้เวลา a, b,

• return (((a mod m) - (b mod m)) + m) mod m

• กำหนดฟังก์ชัน mul() ซึ่งจะใช้ a, b,

• กลับ ((a mod m) * (b mod m)) mod m

• จากวิธีหลัก ให้ทำดังนี้ −

• จัดเรียงอาร์เรย์ a

• ตอบ :=0

• n :=ขนาดของ a

• rcnt :=1

• สำหรับการเริ่มต้น 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 mod 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}

ผลลัพธ์

6