| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 1 | 1 | 1 | 100.000% |
TL;DR Permutation pattern is a permutation with 0 as a wildcard. You are given a permutation pattern. For each index, find its expected cycle size if a random permutation conforming to the pattern is chosen and output it modulo $998\,244\,353$.
And now five times as long, three times as formal
A permutation is an array $p$ of length $n$, such that $\forall_{i \neq j}: p_i \neq p_j, \forall_i: 1 \leq p_i \leq n$
The product of permutations $p$ and $q$ which have the same length, denoted as $p \cdot q$ is the permutation r of the same length as both $p$ and $q$, such that $\forall_i: r_i = p_{q_i}$
The power $p^k$ where $p$ is a permutation and $k$ is a positive integer is
Cycle size of index i is the minimal positive integer k, such that $(p^k)_i = i$. It can be shown that such number always exists.
Permutation pattern is an array of length $n$ such that $\forall_{i \neq j}: a_i = 0 or a_i \neq a_j, \forall_i: 0 \leq a_i \leq n$.
We say permutation $p$ conforms to the pattern $t$ if $\forall_i: p_i = t_i or t_i = 0$.
Let $ans_i$ be the expected cycle size of index i in a random permutation conforming to the pattern given in input. You are to find $ans_i$ modulo $998\,244\,353$.
Taking a potentially non-integer number $X$ modulo $M$ is the following procedure:
Jury guarantees that $X$ is equal to some irreducible fraction $\frac{P}{Q}$ where Q has an inverse modulo $M$. In that case $X$ modulo $M = A$, where $A$ is an integer between 0 and $M - 1$ inclusive and $P - QA$ is divisible by $M$. It can be shown that $A$ is unique.
The first line contains one integer $n$ ($1 \leq n \leq 10^6$), the length of the permutation pattern.
The second line contains $n$ space separated integers $t_i$ ($0 \leq t_i \leq n$).
It is guaranteed that $t$ is a permutation pattern.
Output $n$ integers. $i$-th of them must be equal to $ans_i$ modulo $998\,244\,353$.
5 2 3 4 5 0
5 5 5 5 5
2 0 0
499122178 499122178
6 3 0 1 6 5 2
2 3 2 3 1 3
In the second example both $ans_i$ are equal to $\frac{3}{2}$ which equals 499122178 modulo 998244353.