SamCoding Round 7 (Div. 2) F - Subarrays Divisible by K
- サイト
- SamCoding
- コンテスト
- SamCoding Round 7 (Div. 2)
- 問題
- F - Subarrays Divisible by K(常設版)
長さ の数列 と整数 が与えられます。連続する部分列 のうち、総和が で割り切れるものの個数を求める問題です(、、)。
累積和を 、 とすると、区間 の総和は です。これが で割り切れるのは
のときです。つまり、 で と が等しい組 の個数が答えです。
の順に見ていき、それまでに出てきた余りの個数を数えておけば、各 について「 と同じ余りの が前に何個あったか」がすぐに分かります。全体で です。
Python
from collections import Counter
N, K = map(int, input().split())A = list(map(int, input().split()))t = 0C = Counter()C[0] += 1ans = 0for a in A: t += a t %= K ans += C[t] C[t] += 1print(ans)t が累積和を で割った余り、C が余りごとの出現回数です。最初に C[0] += 1 で の分を数えておき、各要素を足すたびに同じ余りの個数を答えに加えています。
は最大 なので、配列ではなく Counter(辞書)で数えています。