原题地址这是个超级大水题，我太沙茶了，想傻了N久……后来才反应过来……所以要写一下作为警示。
首先这个序列就是一个堆……
因此，问题也就是说N个结点，权值刚好取遍1~N的堆的总数……
设结果为F[N]。设N个结点的堆，左子树有l个结点，右子树有r个结点（显然有l+r+1=N），则有
F[N]=C(N-1, l) * F[l] * F[r]
这个理解起来很容易囧……因为根结点只能是1，左子树和右子树显然也都是堆，因此相当于在2~N中取l个数组成左子树，剩下的数组成右子树……又因为不管取哪些数，左右子树的组成方法总数都是F[l]、F[r]（只与次序有关）……这样就得到上面的式子了囧……
C(N-1, l)=N! / l! / r!，因此需要预处理出来A[i] = i! mod P，然后除法用逆元就行了囧……
不过，本沙茶一开始想按照层数枚举，然后相乘……自然搞不出来囧……后来又用暴力把N<=15的结果拿出来分析，想找到规律……结果毫无规律……后来又纠结了N久才想到上面这个……真正比赛的时候就悲剧了囧……所以要警示一下……
代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 1000010, INF = ~0U >> 2;
int n;
ll MOD, A[MAXN], F[MAXN], res;
void init()
{
cin >> n >> MOD;
}
void prepare()
{
A[0] = A[1] = 1; re3(i, 2, n) A[i] = (A[i - 1] * i) % MOD;
}
void exgcd(ll a, ll b, ll &x, ll &y)
{
if (b) {
ll _x, _y; exgcd(b, a % b, _x, _y);
x = _y; y = _x - (a / b) * _y;
} else {x = 1; y = 0;}
}
void solve()
{
F[0] = F[1] = 1; int s = 1, l = 0, r = 0; ll x, y;
re3(i, 2, n) {
if (l == s) {
if (r == s) {s += s + 1; l++;} else r++;
} else l++;
F[i] = F[l] * F[r] % MOD; F[i] = F[i] * A[i - 1] % MOD;
exgcd(A[l], MOD, x, y); F[i] = F[i] * x % MOD; if (F[i] < 0) F[i] += MOD;
exgcd(A[r], MOD, x, y); F[i] = F[i] * x % MOD; if (F[i] < 0) F[i] += MOD;
}
res = F[n];
}
void pri()
{
cout << res << endl;
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}