Almost Perfect
Contest: Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
Difficulty rating: 2400
Tags: combinatorics, fft, math

A permutation $$$p$$$ of length $$$n$$$ is called almost perfect if for all integer $$$1 \leq i \leq n$$$, it holds that $$$\lvert p_i - p^{-1}_i \rvert \le 1$$$, where $$$p^{-1}$$$ is the inverse permutation of $$$p$$$ (i.e. $$$p^{-1}_{k_1} = k_2$$$ if and only if $$$p_{k_2} = k_1$$$).

Count the number of almost perfect permutations of length $$$n$$$ modulo $$$998244353$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of each test case follows.

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the length of the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of almost perfect permutations of length $$$n$$$ modulo $$$998244353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For $$$n = 2$$$, both permutations $$$[1, 2]$$$, and $$$[2, 1]$$$ are almost perfect.

For $$$n = 3$$$, there are only $$$6$$$ permutations. Having a look at all of them gives us:

- $$$[1, 2, 3]$$$ is an almost perfect permutation.
- $$$[1, 3, 2]$$$ is an almost perfect permutation.
- $$$[2, 1, 3]$$$ is an almost perfect permutation.
- $$$[2, 3, 1]$$$ is NOT an almost perfect permutation ($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2$$$).
- $$$[3, 1, 2]$$$ is NOT an almost perfect permutation ($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2$$$).
- $$$[3, 2, 1]$$$ is an almost perfect permutation.

So we get $$$4$$$ almost perfect permutations.

Example input:
3
2
3
50

Example output:
2
4
830690567

Editorial:
Key fact: There are only $$$3$$$ kinds of cycles in almost perfect permutations: $$$(i)$$$, $$$(i, j)$$$ and $$$(i, j, i + 1, j + 1)$$$.
Proof:
• Cycle size cannot be $$$3$$$: Take $$$(a, b, c)$$$ as a cycle with $$$a < b < c$$$, then $$$p_b = a$$$, $$$p^{-1}_b = c$$$, but $$$a < b < c$$$ implies $$$\lvert a - c \rvert > 1$$$.
• Cycle size cannot be more than $$$4$$$: Let $$$(a_1, a_2, a_3, a_4, a_5, \ldots, a_k)$$$ be consecutive elements of a cycle with size $$$k$$$ ($$$k \geq 5$$$). This means $$$a_1 \ne a_5$$$, but $$$\lvert a_1 - a_3 \rvert = 1$$$ and $$$\lvert a_3 - a_5 \rvert = 1$$$. For now assume $$$a_1 - a_3 = 1$$$ (proof of $$$a_1 - a_3 = -1$$$ is very similar). This means $$$a_3 - a_5 = 1$$$ (as $$$a_1 \ne a_5$$$) and similarly $$$a_7 - a_5 = 1$$$ and so on (if $$$k \leq 6$$$, $$$a_7$$$ is basically $$$a_{7 \bmod k}$$$; i.e. it wraps around). Now, we observe that if $$$a_1 = x$$$, then $$$a_3 = x - 1$$$, $$$a_5 = x - 2$$$, $$$a_7 = x - 3$$$. Therefore $$$a_{k + 1} = x - (k + 1)$$$. But since that cycle is of size $$$k$$$, $$$a_{k + 1}$$$ = $$$a_j$$$, for some $$$j \leq k$$$. Therefore $$$(x - (k + 1)) = (x - j)$$$, for some $$$j \leq k$$$; which means $$$(k + 1) \leq k$$$ — A contradiction.
• works for any $$$2$$$ sized cycles $$$(i, j)$$$: Proof is trivial.
• works for any $$$4$$$ sized cycles $$$(i, j, i + 1, j + 1)$$$: Proof is trivial.
• works only for $$$4$$$ sized cycles $$$(i, j, i + 1, j + 1)$$$: Consider cycle $$$(a, b, c, d)$$$. $$$\lvert a - c \rvert = 1$$$, $$$\lvert b - d \rvert = 1$$$. WLOG assume $$$a < c$$$ (therefore $$$c = a + 1$$$).   Case I : $$$b < d$$$. therefore cycle is $$$(a, b, a + 1, b + 1)$$$ — of the given form.  Case II: $$$b > d$$$. therefore cycle is $$$(a, d + 1, a + 1, d)$$$, which is same as $$$(d, a, d + 1, a + 1)$$$ — also of the given form.
• Case I : $$$b < d$$$. therefore cycle is $$$(a, b, a + 1, b + 1)$$$ — of the given form.
• Case II: $$$b > d$$$. therefore cycle is $$$(a, d + 1, a + 1, d)$$$, which is same as $$$(d, a, d + 1, a + 1)$$$ — also of the given form.
—————————-
Solution 1:
Special thanks to [user:Um_nik] for sharing this solution!
Let's call $$$(i)$$$ as type $$$1$$$ cycles, $$$(i,j)$$$ as type $$$2$$$ cycles and $$$(i,j,i+1,j+1)$$$ as type $$$3$$$ cycles.
What we will do, is we will fix the number of type $$$3$$$ and type $$$2$$$ cycles and come up with a formula.
Let's say there are $$$s$$$ type $$$3$$$ cycles. We need to pick $$$2s$$$ numbers from $$$[1,n-1]$$$ such that no two are adjacent. The number of ways to do this is $$$\binom{n-2s}{2s}$$$. Then we can permute these numbers in $$$(2s)!$$$ ways and group the numbers in pairs of two, but these $$$s$$$ pairs can be permuted to get something equivalent, so we need to divide by $$$s!$$$. Hence we get:
$$$$$$\begin{aligned}\binom{n - 2s}{2s} \frac{(2s)!}{s!} \end{aligned}$$$$$$
Now, for the remaining $$$(n - 4s)$$$ elements, we know that only cycles will be of length $$$2$$$ or $$$1$$$. Let $$$I_k$$$ denote the number of permutations with cycles only of length $$$2$$$ and $$$1$$$. Then the final answer would be
$$$$$$\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\binom{n - 2s}{2s} \frac{(2s)!}{s!} I_{n - 4s}} \end{aligned}$$$$$$
Now, we would be done if we found out $$$I_k$$$ for all $$$k \in \{1, 2, ... n\}$$$. Observe that $$$I_1 = 1$$$ and $$$I_2 = 2$$$. Further for $$$k > 2$$$, the $$$k$$$-th element can appear in a cycle of length $$$1$$$, where there are $$$I_{k - 1}$$$ ways to do it; and the $$$k$$$-th element can appear in a cycle of length two, which can be done in $$$(k - 1) \cdot I_{k - 2}$$$ ways. Therefore we finally have:
$$$$$$\begin{aligned} I_k = I_{k - 1} + (k - 1) \cdot I_{k - 2}\end{aligned}$$$$$$
This completes the solution. Time complexity: $$$\mathcal{O}(n)$$$.
—————————-
Solution 2:
Using the observations in Solution 1 this can be reduced to a counting problem using generating functions. Details follow.
Now, from the remaining $$$n-4s$$$ numbers, let's pick $$$2k$$$ numbers to form $$$k$$$ type $$$2$$$ cycles. We can do this in $$$\binom{n-4s}{2k}$$$ ways. Like before, we can permute them in $$$(2k)!$$$ ways, but we can shuffle these $$$k$$$ pairs around so we have to divide by $$$k!$$$. Also, $$$(i,j)$$$ and $$$(j,i)$$$ are the same cycle, so we also need to divide by $$$2^k$$$ because we can flip the pairs and get the same thing.
Finally, we have the following formula:
$$$$$$\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\sum_{k=0}^{\lfloor \frac{n-4s}{2} \rfloor}{\frac{(2s)!}{s!}\binom{n-2s}{2s}\binom{n-4s}{2k}\frac{(2k)!}{2^k k!}}} \end{aligned}$$$$$$
We can simplify this to get,
$$$$$$\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\frac{(n-2s)!}{s!}\sum_{k=0}^{\lfloor \frac{n-4s}{2} \rfloor}{\frac{1}{2^k (n-4s-2k)! k!}}} \end{aligned}$$$$$$
Now, observe that the answer is in the form of two nested summations. Let us focus on precomputing the inner summation using generating functions. We define the following generating function:
$$$$$$\begin{aligned} P(x) &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{1}{2^k (r-2k)! k!}} \Bigg) } x^r \\ &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^r}{2^k (r-2k)! k!}} \Bigg) } \\ &=\sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^{(r - 2k)}}{(r-2k)!} \cdot \frac{x^{2k}}{2^k k!}} \Bigg) } \\ &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^{(r - 2k)}}{(r-2k)!} \cdot \frac{\big(\frac {x^2}{2} \big)^k}{k!}} \Bigg) } \\ &= \Bigg(\sum_{i \ge 0}{\frac{x^{i}}{i!} \Bigg)} \cdot \Bigg( \sum_{j \ge 0}{ \frac{\big(\frac {x^2}{2} \big)^j}{j!}} \Bigg) \\ P(x) &= \big(e^x \big) \cdot \big( e^{\frac {x^2}{2}} \big) = e^{x + \frac{x^2}{2}} \end{aligned} $$$$$$
We can compute the first few terms of $$$e^x = \sum_{i \ge 0}{\frac{x^{i}}{i!}}$$$ and $$$e^{\frac {x^2}{2}} = \sum_{j \ge 0}{ \frac{x^{2j}}{2^j j!}}$$$; and using FFT, we can multiply these (in $$$\mathcal O(n \log n)$$$ time) to get the first few terms of $$$P(x) = e^{x + \frac{x^2}{2}}$$$.
Finally, we can get the answer (in $$$\mathcal O(n)$$$ time) as,
$$$$$$\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\frac{(n-2s)!}{s!} \Big([x^{n-4s}] P(x) \Big)} \end{aligned}$$$$$$
where $$$[x^m]F(x)$$$ is the coefficient of $$$x^m$$$ in the Taylor expansion of $$$F(x)$$$.
Time complexity: $$$\mathcal{O}(\max{(t_i)}\log{\max{(t_i)}} + \sum{t_i})$$$, where $$$t_i$$$ is the value of $$$n$$$ in the $$$i$$$-th test case.