Codeforce Round #400 C 签到题_codeforces签到题

题目链接：点击打开链接

题目大意：

一个区间的价值【L,R】表示区间内所有元素的价值和。

问你一共有多少个区间的价值，是K的非负整数次幂（0,1,2,3,4,5............）。

题解：计算前缀和，并将已计算的前缀和放入map中储存，对于每个新的前缀和，只需去map中查找是否有满足条件的前缀和即可。

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
const ll INF = 1e14 + 20;
int n,k;
ll a[maxn],ans = 0;
ll nums[51],ncnt;
map<ll,int> map1;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;i++) scanf("%I64d",&a[i]);
	if(k == 1) {ncnt = 1;nums[1] = 1;}
	else if(k == -1) {ncnt = 2;nums[1] = -1;nums[2] = 1;}
	else {
		ll temp = 1;
		for(ncnt = 1;temp <= INF;ncnt++){
			nums[ncnt] = temp;
			temp *= k;
		}ncnt--;
	}
	ll sum = 0;ans = 0;
	map1[0] = 1;
	for(int i = 1;i <= n;i++){
		sum += a[i];
		for(int j = 1;j <= ncnt;j++){
			if(map1.count(sum - nums[j]))	ans += map1[sum - nums[j]];
		}
		map1[sum]++;
	}
	printf("%I64d\n",ans);
	return 0;
}