Almost Perfect (Codeforces 1726E)
Tags: Math, fft

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: 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: For each test case, output a single integer — the number of almost perfect permutations of length $$$n$$$ modulo $$$998244353$$$.

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.

Sample Inputs:
3
2
3
50

Sample Outputs:
2
4
830690567

Solution (Python):
mod = 998244353
N = 3 * 10 ** 5 + 100
fact = [1] * (N + 1)
factinv = [1] * (N + 1)
for i in range(2, N + 1):
    fact[i] = fact[i - 1] * i % mod
factinv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(N - 1, 1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % mod
I = [0] * (N + 1)
I[0] = 1
I[1] = 1
for i in range(2, N + 1):
    I[i] = (I[i - 1] + (i - 1) * I[i - 2]) % mod
T = int(input())
for _ in range(T):
    n = int(input())
    ans = 0
    for k in range(n // 4 + 1):
        ans += fact[n - 2 * k] * factinv[k] % mod * factinv[n - 4 * k] % mod * I[n - 4 * k]
        ans %= mod
    print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
l = 300005
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1] % mod)
dp1 = [1] * (l + 1)
dp1[l] = 1
for i in range(1, l + 1):
    dp1[i] = dp1[i - 1] * i % mod if i % 2 else dp1[i - 1]
dp2 = [0] * (l + 1)
(dp2[0], dp2[1]) = (1, 1)
for i in range(2, l + 1):
    dp2[i] = ((i - 1) * dp2[i - 2] % mod + dp2[i - 1]) % mod

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    ans0 = 0
    for i in range(n // 4 + 1):
        c0 = pow2[i] * comb(n - 2 * i, 2 * i) % mod * dp1[2 * i] % mod
        ans0 += c0 * dp2[n - 4 * i] % mod
        ans0 %= mod
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
mod = 998244353
N = 3 * 10 ** 5 + 100
fact = [1] * (N + 1)
factinv = [1] * (N + 1)
for i in range(2, N + 1):
    fact[i] = fact[i - 1] * i % mod
factinv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(N - 1, 1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % mod
I = [0] * (N + 1)
I[0] = 1
I[1] = 1
for i in range(2, N + 1):
    I[i] = (I[i - 1] + (i - 1) * I[i - 2]) % mod
T = int(input())
for _ in range(T):
    n = int(input())
    ans = 0
    for k in range(n // 4 + 1):
        ans += fact[n - 2 * k] * factinv[k] % mod * factinv[n - 4 * k] % mod * I[n - 4 * k]
        ans %= mod
    print(ans)