C++ で記述され、合計が k^m (m >= 0) となる部分配列の数を求めます。

この記事では、C で合計が k^m, m >= 0 となる部分配列の数を求める方法についてすべて説明します。配列 arr[] と整数 K が与えられた場合、K^m (m は 0 以上) の形式の合計で部分配列の数を見つける必要があります。または、次の式で部分配列の数を見つける必要があると言えます。 K^m の形式の合計 数量の合計は、K の非負のべき乗に等しくなります。

Input: arr[] = { 2, 2, 2, 2 } K = 2

Output: 8

Sub-arrays with below indexes are valid:
[1, 1], [2, 2], [3, 3], [4, 4], [1, 2],
[2, 3], [3, 4], [1, 4]

Input: arr[] = { 3, -6, -3, 12 } K = -3

Output: 3

主に 2 つの方法があります -

ブルート フォース攻撃

この方法では、すべてのサブ配列をループして、それらが K であるかどうかを確認します。 、次にカウントをインクリメントします。

例

#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int main(){
   int arr[] = {2, 2, 2, 2}; // given array
   int k = 2; // given integer
   int n = sizeof(arr) / sizeof(arr[0]); // the size of our array
   int answer = 0; // counter variable
   for(int i = 0; i < n; i++){
      int sum = 0;
      for(int j = i; j < n; j++){ // this will loop will make all the subarrays
         sum += arr[j];
         int b = 1;
         while(b < MAX && sum > b) // k^m Max should be 10^6
            b *= k;
         if(b == sum) // if b == sum then increment count
            answer++;
      }
   }
   cout << answer << "\n";
}

出力

8

ただし、プログラムの時間計算量は O(N*N*log (K )), 、N は配列のサイズ、K は配列のサイズです。ユーザーが指定した整数。

この複雑さは良くありません。なぜなら、この複雑さはより高い制約に使用できるからです。制約が大きい場合、処理に時間がかかりすぎるため、別のアプローチを試します。このプログラムを使用して、より高い制約を達成できるようにします。制約。

効率的な方法

この方法では、プレフィックスの合計とマッピングを使用して処理を削減し、それによって時間の複雑さを大幅に軽減します。

例

#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;
int main(){
   int arr[] = {2, 2, 2, 2}; // The given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int k = 2; // given integer
   ll prefix_sum[MAX];
   prefix_sum[0] = 0;
   partial_sum(arr, arr + n, prefix_sum + 1); // making prefix sum array
   ll sum;
   if (k == 1){
   // we are going to check separately for 1
      sum = 0;
      map<ll, int> m;
   for (int i = n; i >= 0; i--){
      // If m[a+b] = c, then add c to the current sum.
      if (m.find(prefix_sum[i] + 1) != m.end())
         sum += m[prefix_sum[i] + 1];
         // Increase count of prefix sum.
         m[prefix_sum[i]]++;
      }
      cout << sum << "\n";
   }
   else if (k == -1){
      // we are going to check separately for -1
      sum = 0;
      map<ll, int> m;
      for (int i = n; i >= 0; i--){
         // If m[a+b] = c, then add c to the current sum.
         if (m.find(prefix_sum[i] + 1) != m.end())
            sum += m[prefix_sum[i] + 1];

         if (m.find(prefix_sum[i] - 1) != m.end())
            sum += m[prefix_sum[i] - 1];

         // Increase count of prefix sum.
         m[prefix_sum[i]]++;
      }
      cout << sum << "\n";
   }
   else{
      sum = 0;
      ll b;
      map<ll, int> m;
      for (int i = n; i >= 0; i--){
         b = 1;
         while (b < MAX){ // we are not going to check for more than 10^6
            // If m[a+b] = c, then add c to the current sum.
            if (m.find(prefix_sum[i] + b) != m.end())
               sum += m[prefix_sum[i] + b];
               b *= k;
         }
         m[prefix_sum[i]]++;
      }
      cout << sum << "\n";
   }
   return 0;
}

出力

8

結論

合計が k^m の形式になる部分配列の数を求める問題を解決しました。 m >= 0、時間計算量は O(nlog(k)log(n)) 時間計算量です。また、この問題を解決する C プログラムと、この問題を解決する完全な方法 (通常かつ効率的) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ で記述され、合計が k^m (m >= 0) となる部分配列の数を求めます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。