# Molly‘s Chemicals （前缀和+map用法，直接对应答案）

presum[i]-presum[j]=k^x;

presum[i]=k^x+presum[j]；

``````	for(int i=1;i<=64;i++){
excel[0]=1;
if(excel[i-1]<inf) excel[i]=excel[i-1]*k;``````

k^x+presum[j]有多少个

``````for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
for(int j=0;j<=64&&excel[j]<inf;j++){
if(k==1||k==-1){
if(k==-1) mp[presum[i-1]-1]++;
mp[presum[i-1]+1]++;
break;
}
else{
mp[presum[i-1]+excel[j]]++;
}
}
presum[i]=presum[i-1]+a[i];
ans += mp[presum[i]];
}
``````

-1的情况要特判一下吗？

ac代码：

``````#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <string.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5+10;
const ll inf = 1e15 + 10;
ll presum[maxn],a[maxn];
ll excel[maxn];
/*

presum[j]-presum[i]=k^n;
k^n我打算用快速幂打表存储
presum[j]-presum[i]就看

*/
//unmap<ll ll>mp;
map<ll,ll>mp;

ll ksm(ll a,ll b){
ll ans = 1;
for(;b>0;b /=2 , a*= a){
if(b % 2 != 0){
ans *= a;
}
}
return ans;
}

int main() {
int n,k;
ll ans=0;
mp.clear();
memset(excel, 0, sizeof(excel));
memset(presum, 0, sizeof(presum));
memset(a, 0, sizeof(a));
scanf("%d%d",&n,&k);
for(int i=1;i<=64;i++){
if(excel[i-1]<inf) excel[i]=ksm(k,i);
}

for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
for(int j=0;j<=64&&excel[j]<inf;j++){
if(k==1||k==-1){
if(k==-1) mp[presum[i-1]-1]++;
mp[presum[i-1]+1]++;
break;
}
else{
mp[presum[i-1]+excel[j]]++;
}
}
presum[i]=presum[i-1]+a[i];
ans += mp[presum[i]];
}
printf("%lld",ans);
return 0;
}``````

THE END