| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 51 | 19 | 19 | 46.341% |
Andrew is a very curious student who drew a circle with the center at (0, 0) and an integer circumference of C ≥ 3. The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.
Andrew drew N ≥ 3 points at integer locations. In particular, the ith point is drawn at location Pi (0 ≤ Pi ≤ C − 1). It is possible for Andrew to draw multiple points at the same location.
A good triplet is defined as a triplet (a, b, c) that satisfies the following conditions:
Lastly, two triplets (a, b, c) and (a', b', c') are distinct if a ≠ a', b ≠ b', or c ≠ c'.
Andrew, being a curious student, wants to know the number of distinct good triplets. Please help him determine this number.
The first line contains the integers N and C, separated by one space.
The second line contains N space-separated integers. The ith integer is Pi (0 ≤ Pi ≤ C − 1).
Output the number of distinct good triplets.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | 3 ≤ N ≤ 200, 3 ≤ C ≤ 106 |
| 2 | 3 | 3 ≤ N ≤ 106, 3 ≤ C ≤ 6 000 |
| 3 | 6 | 3 ≤ N ≤ 106, 3 ≤ C ≤ 106 P1, P2, . . . , PN are all distinct (i.e., every location contains at most one point) |
| 4 | 3 | 3 ≤ N ≤ 106, 3 ≤ C ≤ 106 |
8 10 0 2 5 5 6 9 0 0
6
Andrew drew the following diagram.
The origin lies strictly inside the triangle with vertices P1, P2, and P5, so (1, 2, 5) is a good triplet. The other five good triplets are (2, 3, 6), (2, 4, 6), (2, 5, 6), (2, 5, 7), and (2, 5, 8).