#PQJ1189x6168. QOJ 1189_6168
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。