CF1089I.Interval-Free Permutations

考虑一个由 $1$ 到 $n$ 的整数构成的排列 $p_1, p_2, \dots, p_n$。我们称排列中的一个子段 $p_l, p_{l+1}, \dots, p_{r-1}, p_r$ 为一个区间，当且仅当它是某一组连续整数的重排。例如，排列 $(6,7,1,8,5,3,2,4)$ 包含区间 $(6,7)$、$(5,3,2,4)$、$(3,2)$ 等。

每个排列都包含一些平凡区间——即整个排列本身和每一个单独的元素。我们称一个排列为无区间排列（interval-free），如果它没有非平凡区间。换句话说，无区间排列不包含长度在 $2$ 到 $n-1$ 之间的区间。

你的任务是，计算长度为 $n$ 的无区间排列的个数，并对质数 $p$ 取模。

输入的第一行包含两个整数 $t$（$1 \le t \le 400$）和 $p$（$10^8 \le p \le 10^9$），分别表示测试用例的数量和取模的质数。接下来的 $t$ 行，每行包含一个整数 $n$（$1 \le n \le 400$），表示排列的长度。

对于每个测试用例，输出一个整数，表示长度为 $n$ 的无区间排列的个数，对 $p$ 取模后的结果。

对于 $n=1$，唯一的排列是无区间排列。对于 $n=4$，有两个无区间排列，分别为 $(2,4,1,3)$ 和 $(3,1,4,2)$。对于 $n=5$，有 $(2,4,1,5,3)$、$(2,5,3,1,4)$、$(3,1,5,2,4)$、$(3,5,1,4,2)$、$(4,1,3,5,2)$ 和 $(4,2,5,1,3)$ 六种。我们不会列出 $n=9$ 时的全部 $28146$ 个无区间排列，但例如 $(4,7,9,5,1,8,2,6,3)$、$(2,4,6,1,9,7,3,8,5)$、$(3,6,9,4,1,5,8,2,7)$ 和 $(8,4,9,1,3,6,2,7,5)$ 都是无区间排列。

当 $n=20$ 时，无区间排列的精确数量为 $264111424634864638$。

由 ChatGPT 4.1 翻译