#PQJ1189x6168. QOJ 1189_6168

    ID: 2560 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:FJOI 2020动态规划数学

QOJ 1189_6168

给定四个栈 𝑎 , 𝑠 1 , 𝑠 2 , 𝑏 , 初始时栈 𝑎 包含 𝑛 个元素,从底到顶依次为 1 , 2 , ⋯ , 𝑛 , 而 𝑠 1 , 𝑠 2 , 𝑏 均为空

你可以进行若干次以下操作:

若 𝑎 非空,将 𝑎 栈顶移动到 𝑠 1 栈顶; 若 𝑠 1 非空,将 𝑠 1 栈顶移动到 𝑠 2 栈顶; 若 𝑠 2 非空,将 𝑠 2 栈顶移动到 𝑏 栈顶;

但是你有一个额外的要求:任意时刻, 𝑠 2 从栈顶到栈底的值必须单调递减

最终,所有元素均在 𝑏 中,把它当作序列从顶到底写出来。

异构序列码性态问题:求有多少个排列不能得到,对质数 𝑀 取模。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含两个整数 𝑁 , 𝑀 。

输出格式

对于每组测试数据,输出一行一个整数,表示答案。

样例数据 样例输入 4 998244353 5 1000000007 6 1000000009 样例输出 2 30 326 子任务

对于 50 % 的数据, 𝑁 ≤ 5 000 。

对于 100 % 的数据, 1 ≤ 𝑁 ≤ 5 × 10 5 。

注 赛时并未提供数据组数,“请选手自行评估”。 赛时并未提供模数 𝑀 的范围,“请选手自行评估”。 赛时并未提供空间限制,“请选手自行评估” QOJ 上设置为 1 GB。