ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) C. Molly’s Chemicals

cf开virtual写到这道题的时候感觉题面很简单，感觉上和自己昨天写的一道莫队的题目很相似，那道题目是让你找有多少个区间的区间和是0，这道题是找有多少个区间的区间和是k的整数次幂。

这道题的n的范围是1e5，那莫队nsqrt（n）肯定是解决不了的. 仔细想了一下这样找区间多半是O（n）的查询，因为个人感觉在这里二分区间也没啥用。O(n)的查询的话，我们记录一下每一位的前缀和，做差便得到了两个下标间的区间和。

在这里发散一下思维，如果我们用max哈希的记录前缀和数值是否存在，这样对每一位k的幂级数而言，我们只要O(n)的就能找出是否存在该区间和。

k的范围是[-10～10]真的是深坑啊，在预处理k的幂级数的时候忘了考虑-1和1的情况了，导致一直while死循环re了5发⊙︿⊙ 这样最多62n的时间复杂度下便可得到正解。

唉，这题wa了11发才过，最近的bug率很高啊，该调整心态了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
using namespace std;
typedef long long ll;

#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson  root << 1
#define rson  root << 1 | 1



ll n,k;

ll a[100005];

map<ll,ll> mp;

vector<ll> mi;



ll powmod(ll a,ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1)
        {
            ans = (ans*a);
            b--;
        }
        b/=2;
        a = a*a;
    }
    return ans;
}

void init(ll k)
{
    int cnt=0;
    while(1)
    {
        //cout<<111<<endl;
        if(k==-1)
            mi.push_back(-1);
        if(k==-1||k==1)
        {
            mi.push_back(1);
            break;
        }
        else
        {
            mi.push_back(powmod(k,cnt));
            cnt++;
            //cout<<pos<<endl;
            ll shu=powmod(k,cnt-1);
            if(shu>=1e15)
                break;
        }
    }
}

int main()
{
    //cout<<powmod(-1,2)<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    memset(a,0,sizeof(a));
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    init(k);
    ll sum=0;
    //cout<<mi[0]<<endl;
    //cout<<pos<<endl;
    for(ll i=0; i<mi.size(); i++)
    {
        //cout<<mi[i]<<endl;
        //cout<<111<<endl;
        mp.clear();
        ll pownum=mi[i];
        for(ll j=1; j<=n; j++)
        {
            //cout<<a[j-1]<<endl;
            mp[a[j-1]]++;
            if(mp.count(a[j]-pownum))
            {
                sum+=mp[a[j]-pownum];
                //cout<<mp[a[j]-pownum]<<endl;
            }
        }
    }
    cout<<sum<<endl;
}