AtCoder Regular Contest 187
翻译中…
Problem Statement
翻译中…
You are given a sequence $A = (A_1, \ldots, A_N)$ of length $N$. Here, $N$ is an integer not less than $3$.
翻译中…
You can perform the following operation any number of times (zero or more).
翻译中…
- Choose an integer
$i$satisfying$1 \leq i \leq N$and$A_i = A_{i+1} = A_{i+2}$. Replace two of$A_i$,$A_{i+1}$, and$A_{i+2}$with integers between$1$and$N$, inclusive. Here, assume$A_{N+1} = A_1$and$A_{N+2} = A_2$.
翻译中…
Find the number, modulo $998244353$, of possible resulting sequences $A$ that are permutations of $(1, \ldots, N)$.
翻译中…
Constraints
翻译中…
- All input numbers are integers.
$3 \leq N \leq 5 \times 10^5$$1 \leq A_i \leq N$
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N
A_1 \ldots A_N翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
6
1 2 3 3 1 1
Output #1
360
For example, we can obtain the permutation $A = (1,2,4,3,5,6)$ through the following steps.
- Perform the operation with $i=5$. Replace $A_5$ with $3$ and $A_6$ with $6$. Now, $A = (1,2,3,3,3,6)$.
- Perform the operation with $i=3$. Replace $A_3$ with $4$ and $A_5$ with $5$. Now, $A = (1,2,4,3,5,6)$.
There are $360$ possible resulting sequences $A$ that are permutations of $(1, \ldots, 6)$.
Input #2
5
3 1 3 4 1
Output #2
0
There are no possible resulting sequences $A$ that are permutations of $(1, \ldots, 5)$.
Input #3
10
1 1 1 8 8 8 7 7 7 10
Output #3
604800
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。