| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 512 MB | 10 | 7 | 7 | 87.500% |
Hello sir, I am very interested in coding.. But I am not able to get the solution to a problem. Can you help me??
An array of integers is bad if it contains a pair of equal adjacent elements. An array is good if it is not bad.
You are given a good array. How many ways are there to remove its elements one by one, concatenating the left and right part after each removal, such that at no point the array is bad? Two ways are different if there is a step on which indices of removed elements differ.
For example, after the removal of 1ドル$ from a good array $[2, 1, 2]$ it becomes a bad array $[2, 2]$ and after the removal of 5ドル$ from a good array $[1, 2, 3, 4, 5, 6]$ it becomes $[1, 2, 3, 4, 6]$ and stays good.
Output the answer congruent to the real one modulo 998244353. Formally, if the real answer is $y$ and your answer is $x,ドル it will be considered correct if $-2^{63} \leq x < 2^{63}$ and $x-y$ is divisible by 998244353.
The first line contains a single integer $n$ (1ドル \leq n \leq 500$), the number of elements in the array.
The second line contains $n$ integers $a_i$ (1ドル \leq a_i \leq n$), elements of the array.
Output a single integer --- the answer to the problem modulo 998244353.
3 1 2 3
6
4 1 2 1 2
8
12 1 2 3 1 2 3 1 2 3 1 2 3
25660800
1 1
-998244352
2 1 2
998244355
In the first example all elements are distinct, so it's impossible to get a bad array at some point. That's why there are 3ドル! = 6$ ways to remove all the elements.
In the fourth example the real answer is 1ドル$ because there is only one way to remove the only element. The given answer $-998244352$ is congruent to 1ドル$ modulo 998244353, so it is correct too.
In the fifth example the real answer is 2ドル$.
Sorry for my bad English.