求由\(1-n\)组成的数列\(\{a_i\}\)中，满足\(a_i>a_{i/2}(i\neq 1)\)的数列方案数\(mod\ p\)，\(1 ≤n ≤ 10^6, p≤ 10^9\)。

解

显然此为完全二叉树压维模型，即父节点点权\(a_i\)的子节点点权为\(a_{i/2},a_{i/2+1}\)，满足\(a_i<a_{i/2},a_i<_{i/2+1}\)。

法一：

于是要在二叉树下下功夫，显然不能以序列长度为状态，考虑二叉树通常的子树递推转移，于是设\(f[i]\)表示以节点i为根节点的满足条件的二叉树方案数，显然我们的知道i的左右子树的节点数，而这显然是可以暴力维护的，画张图，按照规律来即可。

设其左子树节点个数l,右子树节点个数r,于是我们有

\[f[i]=f[2i]f[2i+1]\frac{(l+r)!}{l!}=f[2i][2i+1]C_{l+r}^l\]

边界把二叉树最后一层节点都初始化为1即可。

参考代码：

暂缺

法二：

设\(f[i]\)表示有i个节点的二叉树的满足条件的方案数，显然根节点的左右节点的个数l,r可以暴力预处理，于是有

\[f[i]=f[l]f[r]C_{i-1}^l\]

边界:\(f[1]=1\)

参考代码：

#include 
    
     #include 
     
      #define il inline#define ri register#define ll long longusing namespace std;int l[2000001],r[2000001],    dp[1000001],jc[1000001],    jv[1000001],yyb;il void prepare(int);il int C(int,int),pow(int,int);int main(){    int n,i,j;    scanf("%d%intd",&n,&yyb);    for(i=2,prepare(n);(1<
      
       <=n;++i){        int head,mid,tail;        head=1<
       
        <
        
         >1;        for(j=head;j<=mid;++j)            l[j]=l[j-1]+1,r[j]=r[j-1];        for(j=mid+1;j<=tail;++j)            l[j]=l[j-1],r[j]=r[j-1]+1;    }dp[1]=dp[0]=1;    for(i=2;i<=n;++i)        dp[i]=(ll)dp[l[i]]*dp[r[i]]%yyb*C(i-1,l[i])%yyb;    printf("%d",dp[n]);    return 0;}il int pow(int x,int y){    int ans(1);    while(y){        if(y&1)ans=(ll)ans*x%yyb;        x=(ll)x*x%yyb,y>>=1;    }return ans;}il void prepare(int n){    int i;    for(i=jc[0]=1;i<=n;++i)        jc[i]=(ll)jc[i-1]*i%yyb;    --i,jv[i]=pow(jc[i],yyb-2),jv[0]=1;    while(i>1)jv[i-1]=(ll)jv[i]*i%yyb,--i;}il int C(int n,int r){    if(n