No.3516 Very Large Range Mod
タグ : / 解いたユーザー数 19
作問者 :
yu23578
/ テスター :
aa36
Yoyoyo8128
GaLLium
Germanium32
yt142857
Problem Statement
A sequence of positive integers $A$ is represented using sequences of positive integers $B,C$ of length $N$. The length of $A$ is $\sum_{i=1}^{N} B_i$; the first $B_1$ terms of $A$ are $C_1$, the next $B_2$ terms are $C_2$, $\cdots$, and the last $B_N$ terms are $C_N$.
Among the contiguous subarrays of length $K$ contained in the sequence of positive integers $A$, find the number of those whose sum of $K$ elements is a multiple of $M$.Constraints
- $1 \le N \le 2 \times 10^5$
- $1 \le B_i,C_i \le 10^9$
- $1 \le K,M \le 10^9$
- $K \le \sum_{i=1}^{N} B_i$
Input
$N\ K\ M$ $B_1\ B_2\ \cdots\ B_N$ $C_1\ C_2\ \cdots\ C_N$
Output
Output the number of contiguous subarrays satisfying the condition. Print a newline at the end.
Sample
Sample 1
Input
3 2 6 2 2 1 3 2 4
Output
2
The contiguous subarrays of length $K(=2)$ contained in $A(=(3,3,2,2,4))$ are the following $4$:
$(A_1,A_2) = (3,3)$
$(A_2,A_3) = (3,2)$
$(A_3,A_4) = (2,2)$
$(A_4,A_5) = (2,4)$.
The sums of the elements of these contiguous subarrays are $6,5,4,6$, respectively. There are $2$ multiples of $6$, so output $2$.
Sample 2
Input
1 1 1 1000000000 1000000000
Output
1000000000
Sample 3
Input
5 5 5 1 1 1 1 1 1 1 1 1 1
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。