解题报告：题目问的是存在区间使得区间和为k的n次幂的方案数，即s[r]-s[l]==pow(k,i) , 由于i很小，那么我们枚举右端点 通过map来记录前面前缀和出现的次数。
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<map> #include<set> #include<cmath> using namespace std; typedef long long ll; const int N=100010; const int mod=1e9+7; ll s[N]; int n,k; ll a[N]; map<ll,int>mp; vector<ll>Q; int main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin >> n >> k; mp[0]++; ll res=0; for(int i=0;i<60;i++) { Q.push_back((ll)pow(k,i)); if(k==1 ) break; if(k==-1 && i==1) break; if((ll)pow(k,i)>1e14) break; } for(int i=1;i<=n;i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; for(auto x:Q) { res+=mp[s[i]-x]; } mp[s[i]]++; } cout<<res<<endl; return 0; }