Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 776 C. Molly's Chemicals ( Math )

Problem - 776C - Codeforces

題意:
給你一個長度 N 的序列,以及 K。問有多少個區間的總和是 K 的非負整數次方。

制約:
The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection value is a non-negative power of this number k. (1 ≤ n ≤ 1e5, 1 ≤ |k| ≤ 10).
Next line contains n integers a1, a2, ..., an ( - 1e9 ≤ ai ≤ 1e9) — affection values of chemicals.

解法:
考慮 abs( K ) > 1,枚舉所有 K 的非負整數次方,不需要枚舉超過 50 個 ( 2^50 > 1e5 * 1e9 )。再利用前綴和,找後減前恰為 k 的即可。

時間 / 空間複雜度:
O( N lg( MAXA * N ) )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );

int N, K;
int A[ MAXN ];
long long pA[ MAXN + 1 ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> K;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
    pA[ i + 1 ] = pA[ i ] + A[ i ];
  }
  long long ans = 0;
  for( long long k = 1; ; ) {
    static set< long long > vis;
    if( vis.count( k ) ) break;
    vis.emplace( k );
    map< long long, int > cnt;
    for( int i = 1; i <= N; ++i ) {
      ++cnt[ pA[ i - 1 ] ];
      if( cnt.count( pA[ i ] - k ) ) {
        ans += cnt[ pA[ i ] - k ];
      }
    }
    if( fabs( 1.0 * k * K ) > 1e14 ) break;
    k *= K;
  }
  cout << ans << endl;
  return 0;
}