| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 40 | 22 | 17 | 48.571% |
In the best school in Varaždin, there was an excellent computer science teacher known for her interesting and unusual ideas. Her name was Lana, and she often gave her students impossible or unsolvable problem. Each student only needed to solve 1 problem during the school year to pass the class with an excellent grade. Students who did not solve any tasks by the end of the year would have to repeat the grade. On the last day of school, she wrote an extremely difficult problem on the board, which went as follows:
Imagine you have a sequence of numbers of length $N,ドル and you can remove some elements from the beginning or the end (or both). How many ways can you perform such deletions so that after the deletion, there must be at least 1ドル$ number that appears exactly once, at least 1ドル$ number that appears exactly twice, . . ., and at least 1ドル$ number that appears exactly $K$ times.
A student named Fran, who had not solved any problems so far, quickly said, "I know how to solve this problem." Teacher Lana did not believe Fran and told him, "Write the code in the next 30 minutes, and then I’ll believe you. If you don’t, you’ll have to repeat the grade." Fran doesn’t know how to code, so he urgently asked for your help to write the code to solve this task. In his hurry, he forgot to explain his idea for solving the task. Write a code that takes as input the numbers $N$ and $K,ドル the sequence of $N$ elements, and solve Lana’s question to help Fran.
In the first line, there are 2ドル$ positive integers $N$ (1ドル ≤ N ≤ 10^5$) and $K$ (1ドル ≤ K ≤ 4$) from the task description.
In the second line, there are $N$ positive integers $a_i$ (1ドル ≤ a_i ≤ N$), the numbers from the task description.
In the first line, print a whole number, the number of distinct deletions such that the conditions from the task hold. Two deletions are different if there is an index that is not deleted in one, but deleted in the other.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $N ≤ 1000$ |
| 2 | 15 | 1ドル ≤ a_i ≤ k$ for all $i = 1, 2, \dots , N$ |
| 3 | 35 | $K = 1$ |
| 4 | 50 | No additional constraints. |
3 1 1 2 1
6
The possible sequences after deletion are: $[1], [2], [1], [1, 2], [2, 1], [1, 2, 1],ドル and in each of the 6ドル$ sequences, there is a number that appears exactly once.
6 3 6 5 6 4 5 5
1
The only sequence after deletion in which there is at least 1ドル$ number that appears exactly once, at least 1ドル$ number that appears exactly twice, and at least 1ドル$ number that appears exactly three times is the given sequence of $N$ numbers.
6 2 5 4 5 2 6 5
5