コンテンツにスキップ

SamCoding Round 7 (Div. 2) F - Subarrays Divisible by K

サイト
SamCoding
コンテスト
SamCoding Round 7 (Div. 2)
問題
F - Subarrays Divisible by K(常設版)

長さ nn の数列 aa と整数 kk が与えられます。連続する部分列 al,…,ara_l, \ldots, a_r のうち、総和が kk で割り切れるものの個数を求める問題です(n≤105n \le 10^5、k≤109k \le 10^9、0≤ai≤1090 \le a_i \le 10^9)。

累積和を S0=0S_0 = 0、Si=a1+⋯+aiS_i = a_1 + \cdots + a_i とすると、区間 [l,r][l, r] の総和は Sr−Sl−1S_r - S_{l-1} です。これが kk で割り切れるのは

Sr≡Sl−1(modk)S_r \equiv S_{l-1} \pmod{k}

のときです。つまり、0≤i<j≤n0 \le i < j \le n で Si mod kS_i \bmod k と Sj mod kS_j \bmod k が等しい組 (i,j)(i, j) の個数が答えです。

j=0,1,…,nj = 0, 1, \ldots, n の順に見ていき、それまでに出てきた余りの個数を数えておけば、各 jj について「Sj mod kS_j \bmod k と同じ余りの SiS_i が前に何個あったか」がすぐに分かります。全体で O(n)O(n) です。

Python
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
t = 0
C = Counter()
C[0] += 1
ans = 0
for a in A:
t += a
t %= K
ans += C[t]
C[t] += 1
print(ans)

t が累積和を kk で割った余り、C が余りごとの出現回数です。最初に C[0] += 1 で S0=0S_0 = 0 の分を数えておき、各要素を足すたびに同じ余りの個数を答えに加えています。

kk は最大 10910^9 なので、配列ではなく Counter(辞書)で数えています。