Molly's Chemicals

C. Molly's Chemicals

这道题的思路跟C. Summarize to the Power of Two十分的相似。都是要求关于某个数的倍数。

优化方式都是用一个 map 来储存存在的数字，然后用某个数的幂次方减去当前遍历数字，看 map 是否存在有这个值。因为转化为幂次来做的话，幂次这一块复杂度不会超过1e2，而 n 最大为1e5，所以可解。

而该题不同的地方在于，它是一个连续片段，所以我们需要用到前缀和来优化，而且，因为它是连续片段的缘故，所以也只能够遍历一个数字，再在 map 中标记其存在。

for(int i=1;i<=n;++i)
            ans+=m[a[i]-t],m[a[i]]++;

代码：

// Created by CAD on 2020/1/12.
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=1e5+5;
map<ll,int> m;
ll a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;    cin>>n>>k;
    ll sum=0;
    for(int i=1;i<=n;++i)
        cin>>a[i],sum+=abs(a[i]),a[i]+=a[i-1];
    ll t=1,ans=0;
    while(abs(t)<=sum)
    {
        m.clear();
        m[0]=1;
        for(int i=1;i<=n;++i)
            ans+=m[a[i]-t],m[a[i]]++;
        t*=k;
        if(t==1) break;
    }
    cout<<ans<<endl;
    return 0;
}