Codeforces 776C：Molly's Chemicals（思维）

http://codeforces.com/problemset/problem/776/C

题意：给出一个有n个数的序列，还有一个k，问在这个序列中有多少个子序列使得sum[l, r] = k^0,1,2,3……

思路：sum[l, r] = k ^ t, 前缀和sum[r] = sum[l-1] + k^t。即如果后面有一段序列使得sum[l,r] = k^t，那么它可以转化为前缀和相减使得这一段大小为k^t，即sum[i] = sum[j] + k^t (1 <= j < i)。

那么对于处理好的每一个前缀和，直接往后面加上k^t（0<=t<=x,k^x是不超过题目范围的数）。然后在后面遍历的时候直接加上对应那个数的权值。

因为数据很大，所以只能用map来装权值。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 100100
 4 typedef long long LL;
 5 LL n, k;
 6 LL sum[N], b[N], a[N];
 7 map<LL, int> mp;
 8 
 9 int main() {
10     cin >> n >> k;
11     for(int i = 1; i <= n; i++) cin >> a[i], b[i] = b[i-1] + a[i];
12     int cnt = 1;
13     sum[1] = 1;
14     if(k == -1) sum[2] = -1, cnt++;
15     else if(k != 1) {
16         LL tmp = k;
17         while(tmp < 1e15) {
18             sum[++cnt] = tmp;
19             tmp *= k;
20         }
21     } // sum数组装的是k^t
22     // mp代表前缀和的权值
23     for(int i = 1; i <= cnt; i++) mp[sum[i]] = 1; 
24     LL ans = 0;
25     for(int i = 1; i <= n; i++) {
26         ans += mp[b[i]];
27         for(int j = 1; j <= cnt; j++)
28             mp[b[i] + sum[j]]++;
29     }
30     cout << ans << endl;
31     return 0;
32 }