题目翻译

给定长度为 $n$ 的序列 $a$，求有多少组 $(l,r)$ 满足 $\sum\limits_{i=l}^ra_i=k^i$。

题目思路

首先考虑，枚举 $l$ 和 $r$，判断 $\sum\limits_{i=l}^r$ 是否为 $k$ 的倍数。但是显然这种做法复杂度为 $n^2$ 无法通过。

设 $s$ 为 $a$ 的前缀和数组，我们注意到，我们查找 $s_r-s_{l-1}=k^i$，其实等价于找 $s$ 中是否有 $s_r-k^i$ 这个元素，那么我们只需枚举一个端点以及一个 $k$ 的次幂。

显然在这个题中，除去 $k=\pm1$，上述的 $i$ 最多只需枚举至 $\log_2 (10^9\times 10^5)\approx 60$ 次。

因此，总的时间复杂度为 $\mathcal O(n\log V)$。其中 $V=10^9\times 10^5$。对于 C++ 选手，如果你用 map 来判断 $s_r-k^i$ 是否存在还需乘上一个 $\log_2 n$。

完整代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
ll st[100];
int top;
ll pw=1;
ll k,ans;
ll a[100020];
ll s[100020];
map<ll,int>mp;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=a[i]+s[i-1];
    }
    for(int i=0;i<=60;i++)
    {
        if(abs(pw)>1e14)break;
        st[++top]=pw;
        pw*=k;
    }
    mp[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(k==1)ans+=mp[s[i]-1];
        else if(k==-1)ans+=mp[s[i]-1]+mp[s[i]+1];
        else 
        {
            for(int _=1;_<=top;_++)
            {
                ans+=mp[s[i]-st[_]];
            }
        }
        mp[s[i]]++;
    }
    cout<<ans<<endl;
    return 0;
}