| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 5 | 5 | 5 | 100.000% |
In an array containing only positive integers, we say an integer is heavy if it appears more than once in the array, and light otherwise.
An array is good if the integers in the array alternate between light and heavy.
Given an array $a_1, \dots , a_N,ドル count the number of ways to partition it into some number of contiguous subarrays such that each subarray, when considered as an array on its own, is good. As the answer may be large, output it modulo 1ドル,円 000,円 003$.
The first line of input contains a single integer, $N$.
The next line contains $N$ integers $a_1, \dots , a_N$ (1ドル ≤ a_i ≤ N$).
The number of ways to partition the array into good contiguous subarrays, modulo 1ドル,円 000,円 003$.
| Subtask | Score | Bounds on $N$ | Additional constraints |
|---|---|---|---|
| 1 | 3 | 2ドル ≤ N ≤ 50,円 000$ | For each $i,ドル $a_i ≤ 26$. |
| 2 | 4 | 2ドル ≤ N ≤ 5,円 000$ | No additional constraints. |
| 3 | 5 | 2ドル ≤ N ≤ 500,円 000$ | If $i$ is odd, then $a_i = 1$. |
| 4 | 6 | 2ドル ≤ N ≤ 500,円 000$ | Any number appears at most twice in the array. |
| 5 | 7 | 2ドル ≤ N ≤ 500,円 000$ | No additional constraints. |
5 1 2 3 2 3
4
There are four valid partitions of $[1, 2, 3, 2, 3]$:
5 1 2 1 3 1
6