C++ এ পরবর্তী প্রস্থের সমষ্টি

ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে রয়েছে, 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() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) + (b mod m)) mod m

• একটি ফাংশন সাব() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফেরত (((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