原題地址這是個超級大水題，我太沙茶了，想傻了N久……后來才反應(yīng)過來……所以要寫一下作為警示。
首先這個序列就是一個堆……
因此，問題也就是說N個結(jié)點(diǎn)，權(quán)值剛好取遍1~N的堆的總數(shù)……
設(shè)結(jié)果為F[N]。設(shè)N個結(jié)點(diǎn)的堆，左子樹有l(wèi)個結(jié)點(diǎn)，右子樹有r個結(jié)點(diǎn)（顯然有l(wèi)+r+1=N），則有
F[N]=C(N-1, l) * F[l] * F[r]
這個理解起來很容易囧……因?yàn)楦Y(jié)點(diǎn)只能是1，左子樹和右子樹顯然也都是堆，因此相當(dāng)于在2~N中取l個數(shù)組成左子樹，剩下的數(shù)組成右子樹……又因?yàn)椴还苋∧男?shù)，左右子樹的組成方法總數(shù)都是F[l]、F[r]（只與次序有關(guān)）……這樣就得到上面的式子了囧……
C(N-1, l)=N! / l! / r!，因此需要預(yù)處理出來A[i] = i! mod P，然后除法用逆元就行了囧……
不過，本沙茶一開始想按照層數(shù)枚舉，然后相乘……自然搞不出來囧……后來又用暴力把N<=15的結(jié)果拿出來分析，想找到規(guī)律……結(jié)果毫無規(guī)律……后來又糾結(jié)了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;
}