Codeforces Round #400 (Div. 1 + Div. 2, combined) C. Molly’s Chemicals 区间和、构造、前缀的后缀

My Solution

题意：给出n个数字，要求选出一段连续的数字，使它的和为k的非负整数次方，为这样的区间有多少个。

区间和、构造、前缀的后缀

这是一个很有趣的构造题，一个连续区间[a, b]，转化为 [1, b] - [1,a-1],如果差值，满足要求则这样的区间存在，

然后换过来，对于每个k^j,对于 [1,b] - k^j == [1,ax-1],有多少个前缀和sum{[1,ax-1]}就有多少个多少个区间[ax, b] == k^j次。

这里可以借助map来记录 前缀和sum{[1,ax-1]} 出现的次数。

此外要处理2种特殊的情况，一种是k == -1，这时pow_k[j] 只对 -1和1进行讨论， 还有一种是 k == 1，这时pow_k[j]只对 1 进行讨论。

从而巧妙的把这个问题从O(n^2)优化到了O(n)

复杂度 O(n)

#include 
#include 
#include