C++ Số mảng con có tổng dạng k^m (m≥0)

Cho mảng và K, đếm mảng con có tổng bằng K^m với m≥0 (lũy thừa không âm của K). Ví dụ:

Input: {2,2,2,2}, K=2 → Output: 8
Mảng con hợp lệ: [1,1],[2,2],[3,3],[4,4],[1,2],[2,3],[3,4],[1,4]

Input: {3,-6,-3,12}, K=-3 → Output: 3

Phương pháp vét cạn

Kiểm tra mọi mảng con, xem tổng có phải lũy thừa của K không. O(n² log K).

Ví dụ

#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;

int main() {
    int arr[]={2,2,2,2}, k=2, n=4, ans=0;
    for (int i=0; ib) b*=k;
            if (b==sum) ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

Phương pháp hiệu quả: Prefix Sum + Map

Tính prefix sum. Duyệt từ phải sang trái, với mỗi prefix_sum[i], tìm trong map các prefix_sum[j] = prefix_sum[i] + K^m. Xử lý riêng K=1, K=-1, K khác.

Ví dụ

#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;

int main() {
    int arr[]={2,2,2,2}, n=4, k=2;
    ll prefix_sum[MAX];
    prefix_sum[0]=0;
    partial_sum(arr, arr+n, prefix_sum+1);
    ll sum=0;
    map<ll,int> m;

    if (k==1) {
        for (int i=n; i>=0; i--) {
            if (m.count(prefix_sum[i]+1)) sum += m[prefix_sum[i]+1];
            m[prefix_sum[i]]++;
        }
    } else if (k==-1) {
        for (int i=n; i>=0; i--) {
            if (m.count(prefix_sum[i]+1)) sum += m[prefix_sum[i]+1];
            if (m.count(prefix_sum[i]-1)) sum += m[prefix_sum[i]-1];
            m[prefix_sum[i]]++;
        }
    } else {
        for (int i=n; i>=0; i--) {
            ll b=1;
            while (b

Kết quả
8

Kết luận
Đã giải bài toán mảng con tổng = K^m bằng prefix sum + map, độ phức tạp O(n log K log n). Xử lý riêng K=1, -1. Code C++ áp dụng cho C, Java, Python. Hy vọng hữu ích.