= 0>
在本文中，我们将解释有关在 c++ 中求解总和为 k^m, m >= 0 的子数组数量的所有内容。给定一个数组 arr[] 和一个整数 k，我们需要找到具有 k^m 形式的和的子数组的数量，其中 m 大于等于 0，或者我们可以说我们需要找到具有 k^m 形式的子数组的数量总和等于 k 的某个非负幂。
input: arr[] = { 2, 2, 2, 2 } k = 2output: 8sub-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 = -3output: 3
主要有两种方法 -
暴力破解在这种方法中，我们将遍历所有子数组并检查它们是否是k 与否；如果是，则我们增加计数。
示例#include <bits/stdc++.h>#define max 1000000using 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 1000000using 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的详细内容。