题意

定义长度为 $n$ 的排列 $p$ 是合法的当且仅当 $\forall i \in [2,n],p_i > p_{\left \lfloor i/2 \right \rfloor}$。给你 $n,P$，求 $n$ 的排列中合法排列的方案数，模 $P$，保证 $P$ 是质数。

分析

首先注意到，这个神秘的 $p_i > p_{\left \lfloor i/2 \right \rfloor}$ 的限制可以用一个树形结构来表示，表示出来就是一个小根堆，左右儿子是 $2x$ 和 $2x+1$。设 $f_i$ 表示以 $i$ 为根的子树中形成小根堆的方案数，这里方案数不考虑数字具体值，只考虑相对大小。然后设 $sz_i$ 表示以 $i$ 为根的子树大小。

转移就是 $f_i = \begin{pmatrix}sz_{2i}\\sz_i-1\end{pmatrix} \times f_{2i} \times f_{2i+1}$。这里指的就是根节点拿走最小的一个数字，剩下选出 $sz_{2i}$ 个数字给左子树，剩下的给右子树。

如果你这样就写完了，你会发现 WA 了。注意到这题里有可能 $n \ge P$，费马小定理不成立，直接用阶乘预处理就会挂，要用 $\text{Lucas}$ 来做，预处理只要到 $\min(n,P-1)$，否则预处理阶乘逆元时也会错。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 1000005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, P, m, fact[N], inv_fact[N], f[N], sz[N];
il int ksm(int x, int r){
    int ans = 1;
    for (; r; x = 1ll * x * x % P, r >>= 1) if (r & 1) ans = 1ll * ans * x % P;
    return ans;
}
int C(int n, int m, int P){return (n < m ? 0 : 1ll * fact[n] * inv_fact[m] % P * inv_fact[n - m] % P);}
int Lcs(int n, int m, int P){return (n < m ? 0 : !n ? 1 : 1ll * Lcs(n / P, m / P, P) * C(n % P, m % P, P) % P);}
void dfs(int u){
    f[u] = sz[u] = 1;
    if ((u << 1) > n) return ;
    if ((u << 1 | 1) > n) return dfs(u << 1), f[u] = f[u << 1], sz[u] += sz[u << 1], void(0);
    dfs(u << 1), dfs(u << 1 | 1), sz[u] += sz[u << 1] + sz[u << 1 | 1];
    f[u] = 1ll * Lcs(sz[u] - 1, sz[u << 1], P) * f[u << 1] % P * f[u << 1 | 1] % P;
}
int main(){
    n = rd(), P = rd(), fact[0] = 1, m = min(n, P - 1);
    for (int i = 1; i <= m; i++) fact[i] = 1ll * fact[i - 1] * i % P;
    inv_fact[m] = ksm(fact[m], P - 2);
    for (int i = m - 1; i >= 0; i--) inv_fact[i] = 1ll * inv_fact[i + 1] * (i + 1) % P;
    dfs(1);
    printf ("%d\n", f[1]);
    return 0;
}