CF776C Molly‘s Chemicals

解题报告：题目问的是存在区间使得区间和为k的n次幂的方案数，即s[r]-s[l]==pow(k,i) , 由于i很小，那么我们枚举右端点 通过map来记录前面前缀和出现的次数。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=100010;
const int mod=1e9+7;
ll s[N];
int n,k;
ll a[N];
map<ll,int>mp;
vector<ll>Q;
int main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> k;
	mp[0]++;
	ll res=0;
	for(int i=0;i<60;i++)
	{
   
		Q.push_back((ll)pow(k,i));
		if(k==1 )	break;
		if(k==-1 && i==1)	break;
		if((ll)pow(k,i)>1e14)	break;
	}
	for(int i=1;i<=n;i++)
	{
   
		cin >> a[i];
		s[i] = s[i-1] + a[i];
		for(auto x:Q)
		{
   
			res+=mp[s[i]-x];
		}
		mp[s[i]]++;
	}
	cout<<res<<endl;
	return 0;
}