N개의 정수 수열 A1, A2, . . . , AN이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어떤 i, j, k(1 ≤ i < j < k < N)에 대해서 [A1, . . . Ai ], [Ai+1, . . . Aj ], [Aj+1, . . . Ak], [Ak+1, . . . AN ]으로 나눈다.


 예를 들어 주어진 수열이 4, −1, 2, 1, −3, 1, 2, 2, 1, 3이라고 하자. 이 수열을 아래와 같이 나누면 각 부분의 합이 달라서 허용되는 형태가 아니다.
 [4, −1, 2], [1, −3, 1, 2], [2, 1], [3] 


아래과 같이 나눈 경우 각 부분의 합이 모두 같다. 
 [4, −1], [2, 1], [−3, 1, 2, 2, 1], [3] 


아래와 같이 나눈 경우들도 각 부분의 합이 모두 같다.
 [4, −1], [2, 1, −3, 1, 2], [2, 1], [3] 혹은 [4, −1, 2, 1, −3], [1, 2], [2, 1], [3] 


수열을 입력 받아 위와 같이 나눌 수 있는 가능한 방법의 개수를 계산하는 프로그램을 작성하라.

첫 번째 줄에 수열의 길이 N이 주어진다. 
두 번째 줄에 N개의 정수 A1, A2, . . . , AN이 공백 하나씩을 사이로 두고 주어진다.
• 4 ≤ N ≤ 100 000
• 모든 1 ≤ i ≤ N에 대해 −1 000 ≤ Ai ≤ 1 000
(테스트 케이스 비율)
1. (5%) 모든 1 ≤ i ≤ N에 대해 Ai = 0 
2. (7%) 모든 1 ≤ i ≤ N에 대해 Ai > 0 
3. (4%) 모든 1 ≤ i ≤ N에 대해 Ai ≥ 0 
4. (11%) N ≤ 10 
5. (19%) N ≤ 500 
6. (23%) N ≤ 5 000 
7. (31%) 추가 제약 조건 없음

첫 번째 줄에 가능한 방법의 개수를 출력한다. 
출력 값이 매우 클 수 있으므로 C, C++ 언어에서는 long long 형의 변수를, Java에서는 long 형의 변수를 사용해야 한다.

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2021KOI초등1차