#I. Rem of Sum is Num

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Rem of Sum is Num

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

给定一个序列和一个 KK，求这个序列有多少个子区间（子串）满足该区间内所有元素和 SS 除以 KK 的余数是区间长度。

即存在多少对 (l,r)(l,r)，满足 0<r−l+1<K0<r-l+1<K 且 K ∣ ((al+al+1+⋯+ar)−(r−l+1))K\ |\ ((a_l+a_{l+1}+\cdots+a_r)-(r-l+1))。

题目描述

長さ N N の正整数列 A1, A2, … , AN A_1,\ A_2,\ \ldots\ ,\ A_N と正の整数 K K が与えられます。

A A の空でない連続する部分列であって、要素の和を K K で割った余りが要素の数と等しくなるものの数を求めてください。ただし、2 2 つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

输入格式

入力は以下の形式で標準入力から与えられる。

N N K K A1 A_1 A2 A_2 ⋯ \cdots AN A_N

输出格式

条件をみたす部分列の個数を出力してください。

样例 #1

样例输入 #1

5 4
1 4 2 3 5

样例输出 #1

4

样例 #2

样例输入 #2

8 4
4 2 4 2 4 2 4 2

样例输出 #2

7

样例 #3

样例输入 #3

10 7
14 15 92 65 35 89 79 32 38 46

样例输出 #3

8

提示

制約

  • 入力は全て整数である。
  • 1 ≤ N ≤ 2× 105 1\ \leq\ N\ \leq\ 2\times\ 10^5
  • 1 ≤ K ≤ 109 1\ \leq\ K\ \leq\ 10^9
  • 1 ≤ Ai ≤ 109 1\ \leq\ A_i\ \leq\ 10^9

Sample Explanation 1

(1) (1) , (4,2) (4,2) , (1,4,2) (1,4,2) , (5) (5) の 4 4 つが条件をみたす部分列です。

Sample Explanation 2

(4,2) (4,2) が 4 4 回、(2,4) (2,4) が 3 3 回数えられています。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 46ms
  • Powered by Hydro v4.9.27 Community