题解

我们考虑每个数x向2x和2x+1各连一条边，形成一颗根节点的1的树，首先根节点只能选1，假设根节点的左右子树的大小分别是a,b那么左右子树之间的数字大小是互不影响的，那么我们让左边选任意a个数，右边选任意b个数，根节点比这a+b个数都小，然后继续对左右子树递归下去，就能算出所有的方案数。

时间复杂度

$O(n*log(n))$

C++ 代码

#include <iostream>
using namespace std;
const int N=1000010;
typedef long long LL;
int n,p,fac[N],ans;
int inv(int a){
    int b=p-2,res=1;
    while(b){
        if(b&1) res=(LL)res*a%p;
        b>>=1;
        a=(LL)a*a%p;
    }
    return res;
}
int C(int a,int b){
    return (LL)fac[a]*inv(fac[b])%p*inv(fac[a-b])%p;
}
int dfs(int u){
    int a[2],tot=0;
    a[0]=a[1]=0;
    if(u*2<=n) a[tot++]=dfs(u*2);
    if(u*2+1<=n) a[tot++]=dfs(u*2+1);
    ans=(LL)ans*C(a[0]+a[1],a[1])%p;
    return a[0]+a[1]+1;
}
int main(){
    ans=1;
    cin>>n>>p;
    fac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=(LL)fac[i-1]*i%p;
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}