시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 9 | 6 | 6 | 66.667% |
In this problem, we are interested in undirected graphs with $n$ vertices labeled by integers from $1$ to $n$, without loops and parallel edges.
For a given graph $G$, the following procedure can be executed.
function dfs(u) { set u to active for v in 1, 2, ..., n if (u and v are adjacent in G) and (v is inactive) { swap P[u] and P[v] dfs(v) } set u to done } for u in 1, 2, ..., n { set u to inactive set P[u] to u } for u in 1, 2, ..., n if u is inactive: dfs(u)
Given $a_1, a_2, \ldots, a_n$, find the number of different graphs $G$ such that after the procedure, $P[1] = a_1$, $P[2] = a_2$, $\ldots$, and $P[n] = a_n$. Two graphs are different if there is a pair of vertices $(u, v)$ such that one of them contains such edge and the other one does not. As the number of such graphs may be very large, find it modulo $998\,244\,353$.
The first line contains an integer $n$ ($1 \leq n \leq 500$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$). It is guaranteed that each number from $1$ to $n$ occurs in the sequence exactly once.
Print one integer: the number of different graphs $G$ satisfying the conditions, modulo $998\,244\,353$.
3 2 3 1
2
9 7 2 9 1 3 8 6 5 4
3528