CFR 776 C. Molly's Chemicals ( Math )
題意:
給你一個長度 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; }