Codeforce Round #400 C 签到题

题目链接：点击打开链接

题目大意：

一个区间的价值【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 longusing 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;}