[NERC 2018] Interval-Free Permutations

Luogu

IDLGP9799

Time2000ms

Memory512MB

DifficultyP6

2018ICPCNERC/NEERC

我们定义一个从 $1 \sim n$ 的排列是“间隔排列”的情况是，在这个排列中存在连续的一段长度为 $2 \sim n-1$ 的子区间使得这段子区间在排序后是一串连续的自然数。比如，$\{6,7,1,8,5,3,2,4\}$ 是一个“间隔排列”，因为 $\{6,7\}$，$\{5,3,2,4\}$，$\{3,2\}$ 经过排序后都是一段连续的自然数。现在已知 $n$，请你输出**不是**“间隔排列”的排列总数，由于输出可能很大，请对 $p$ 取模。 ## Input 第一行两个整数 $t (1 \leq t \leq 400)$ 和 $p (10^8 \leq p \leq 10^9)$，分别表示数据组数和模数。接下来 $t$ 行，一行一个整数 $n (1 \leq n \leq 400)$。 ## Output 对于每组数据输出 $1 \sim n$ 的所有排列中**不是**“间隔排列”的排列总数对 $p$ 取模的值。 [samples] ## Background 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) I 题。 ## Note 数据保证 $1 \leq t \leq 400$，$10^8 \leq p \leq 10^9$，$1 \leq n \leq 400$。对于样例一的解释：第二组数据存在 $\{2,4,1,3\}$ 和 $\{3,1,4,2\}$ 符合要求。第三组数据存在 $\{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\}$ 满足要求。对于样例二，一共有 $264111424634864638$ 种可能。

Samples

Input #1

4 998244353
1
4
5
9

Output #1

Input #2

1 437122297
20

Output #2

67777575

API Response (JSON)

{
  "problem": {
    "name": "[NERC 2018]  Interval-Free Permutations",
    "description": {
      "content": "我们定义一个从 $1 \\sim n$ 的排列是“间隔排列”的情况是，在这个排列中存在连续的一段长度为 $2 \\sim n-1$ 的子区间使得这段子区间在排序后是一串连续的自然数。比如，$\\{6,7,1,8,5,3,2,4\\}$ 是一个“间隔排列”，因为 $\\{6,7\\}$，$\\{5,3,2,4\\}$，$\\{3,2\\}$ 经过排序后都是一段连续的自然数。 现在已知 $n$，请你输出**不是**“间",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9799"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "我们定义一个从 $1 \\sim n$ 的排列是“间隔排列”的情况是，在这个排列中存在连续的一段长度为 $2 \\sim n-1$ 的子区间使得这段子区间在排序后是一串连续的自然数。比如，$\\{6,7,1,8,5,3,2,4\\}$ 是一个“间隔排列”，因为 $\\{6,7\\}$，$\\{5,3,2,4\\}$，$\\{3,2\\}$ 经过排序后都是一段连续的自然数。\n\n现在已知 $n$，请你输出**不是**“间...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments