/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
非負整数からなる長さ N の列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。
非負整数列からなる長さ 1 以上の列 S=(S _ 1,S _ 2,\ldots,S _ k) のスコアを、列 S _ i\ (1\le i\le k) のうち要素の総和が K で割り切れるものの個数として定めます。
A を 1 つ以上の連続する部分列に分割して得られる非負整数列の列に対するスコアの最大値を求めてください。 ここで、長さ N の列 A を 1 つ以上の連続する部分列に分割するとは、整数からなる長さ 1 以上の列 l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N) をとり、以下のような k 個の列を作ることをいいます。
- (A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k) （ここで、l _ {k+1}=N+1 とする。）
制約
- 1\le N\le2\times10 ^ 5
- 1\le K\le10 ^ 9
- 0\le A _ i\lt K
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A _ 1 A _ 2 \ldots A _ N
出力
答えを出力せよ。
入力例 1
6 10 6 8 2 2 6 4
出力例 1
2
例えば、A を (6),(8,2),(2),(6,4) のように 4 つの連続する部分列に分割することができます。 2 番目と 4 番目の列の要素の総和が 10 の倍数になるので、((6),(8,2),(2),(6,4)) のスコアは 2 です。
スコアが 3 以上になるように A を分割することはできないので、2 を出力してください。
入力例 2
8 1 0 0 0 0 0 0 0 0
出力例 2
8
入力例 3
30 8 5 0 4 2 7 3 2 3 2 4 0 1 4 0 4 1 7 5 2 5 0 3 6 6 2 3 2 2 4 2
出力例 3
8
Score : 450 points
Problem Statement
You are given a sequence of length N consisting of non-negative integers: A=(A _ 1,A _ 2,\ldots,A _ N) .
Define the score of a sequence of length 1 or more consisting of sequences of non-negative integers, S=(S _ 1,S _ 2,\ldots,S _ k), as the number of sequences S _ i\ (1\le i\le k) whose sum of elements is divisible by K.
Find the maximum possible score of a sequence of non-negative integer sequences obtained by dividing A into one or more contiguous subsequences. Here, dividing a sequence A of length N into one or more contiguous subsequences means choosing a sequence of integers l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N) of length 1 or more, and forming the following k sequences.
- (A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k) (Here, let l _ {k+1}=N+1.)
Constraints
- 1\le N\le2\times10 ^ 5
- 1\le K\le10 ^ 9
- 0\le A _ i\lt K
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A _ 1 A _ 2 \ldots A _ N
Output
Output the answer.
Sample Input 1
6 10 6 8 2 2 6 4
Sample Output 1
2
For example, A can be divided into four contiguous subsequences as (6),(8,2),(2),(6,4). The sums of the elements of the second and fourth sequences are multiples of 10, so the score of ((6),(8,2),(2),(6,4)) is 2.
A cannot be divided so that the score is 3 or more, so output 2.
Sample Input 2
8 1 0 0 0 0 0 0 0 0
Sample Output 2
8
Sample Input 3
30 8 5 0 4 2 7 3 2 3 2 4 0 1 4 0 4 1 7 5 2 5 0 3 6 6 2 3 2 2 4 2
Sample Output 3
8