Codeforces Round #400 C 前缀和,思维

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

题意：n个数，问有多少个区间的和是k的次方数，即sum([l, r])=k^x， x>=0。 abs(k)<=10。

tags：一开始O(n^2)统计，果然炸了。。这题要在统计到第 i 个数时，看s[i]-k^x是否在前面出现过。因为k指数增长很快，这样就是O(n)。

// #400
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 2e5+10;

map<ll ,ll >A, vis;
int main()
{
    int n, k, a;
    ll s=0, ans=0;
    scanf("%d %d", &n, &k);
    A[0]++;
    rep(i,1,n) {
        scanf("%d", &a);
        A[s+=a]++;
        vis.clear();
        for(ll j=1; abs(j)<=1e15 && vis[j]==0; j*=k) {      //坑点，因为a[i]<=1e9，但j在这里是指和，所以不是<=1e9
            vis[j]=1;
            if(A.find(s-j)!=A.end()) ans+=A[s-j];
        }
    }
    printf("%lld
", ans);

    return 0;
}