题目大意：给出n个数(a1.....an)，和一个数k，问有多少个区间的和等于k的幂 (1 ≤ n ≤ 10^5, 1 ≤ |k| ≤ 10, - 10^9 ≤ ai ≤ 10^9)
解题思路：首先，可以从题目得出k的幂最大不能超过n*ai=1e14。然后，我们先求出前缀和sum[1]...sum[n]，k的i次幂为power[i]。我们要求出一个区间和等于power[i]即sum[r]-sum[l]=power[i]，转换一下sum[r]=sum[l]+power[i]。
所以我们只需要从1到n遍历一遍，记录下sum[r]的出现次数，用map存起来，即map[sum[i]+power[i]]++。最后如果sum[r]可以从我们的sum[1]到sum[n]这些前缀和里找到，那就把ans+=map[sum[r]]。
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<map> 4 using namespace std; 5 typedef long long ll; 6 const int N = 1e5 + 5; 7 8 ll sum[N];//前缀和 9 ll power[60]; 10 11 int main() { 12 ll n, k; 13 cin >> n >> k; 14 sum[0] = 0; 15 map<ll, ll>mp; 16 for (int i = 1; i <= n; i++) { 17 cin >> sum[i]; 18 sum[i] += sum[i - 1]; 19 } 20 21 ll t = 1; 22 ll cnt = 0; 23 power[0] = 1; 24 //1和-1需要特判 25 if (k == 1 || k == -1) { 26 if (k == -1) { 27 power[1] = -1; 28 cnt++; 29 } 30 } 31 else { 32 for (int i = 1; i <= 50; i++) { 33 t *= k; 34 if (t>1e14) 35 break; 36 power[++cnt] = t; 37 } 38 } 39 //sum[l]=0时的情况 40 for (int i = 0; i <= cnt; i++) { 41 mp[power[i] + 0]++; 42 } 43 44 ll ans = 0; 45 for (int i = 1; i <= n; i++) { 46 //计算ans一定要写在这里 47 ans += mp[sum[i]]; 48 //记录sum[r]=sum[l]+power[j]的出现次数 49 for (int j = 0; j <= cnt; j++) { 50 mp[sum[i] + power[j]]++; 51 } 52 } 53 cout << ans << endl; 54 /*这种写法是错误的，因为sum[r]一定在sum[l]之后，可能出现sum[l]+power[i]得到的值不在sum[l]后面， 55 而在sum[l]前面，那么也就不满足是sum[r]的条件了，下面这样写就会把这种情况也记录在内了。 56 for (int i = 1; i <= n; i++) { 57 ans += mp[sum[i]]; 58 } 59 cout << ans << endl; 60 */ 61 return 0; 62 }