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（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数sub（）を定義します。これには、a、b、

  が必要です。

• return（（（a mod m）-（b mod m））+ m）mod m

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod m）*（b mod m））mod m

• メインの方法から、次のようにします-

• 配列を並べ替える

• ans：=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

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#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