分析：
$O(N)$和$O(NlogN)$的做法很简单就不写了...%了一发神奇的$O(log^3n*$高精度$)$的做法...
考虑我们只能用$2$的整次幂来划分$n$，所以我们从二进制的方面去考虑划分...
定义$g[i][j]$代表的是前$i$个$1$划分完成并且最大的数为$2^j$的方案数，我们枚举前$i-1$个$1$的划分方案来转移：
$g[i][j]=\sum _{k=0}^{j} g[i-1][k]*f[x-k][j-k]$，$x$代表的是第$i$个$1$在第$x$位，$f[i][j]$代表$2^i$的划分方案，并且最大的数字为$2^j$，因为我们要限制$2^x$的划分必须比$2^k$大，所以我们把$2^x$和$2^j$都除以一个$2^k$...
然后$f$数组的转移也是差不多的...
$f[i][j]=\sum_{k=0}^{j} f[i-1][k]*f[i-k-1][j-k]$...
我的高精度写的常数贼大~~~
就当我A了吧...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std; const int maxn=100+5,maxm=200+5,mod=1e9; int tmp; char s[maxn]; struct M{ int len,a[maxm],b[maxm]; inline void init(void){
memset(a,0,sizeof(a));
} friend M operator + (M x,M y){
M res;res.len=max(x.len,y.len);res.init();
for(int i=1;i<=res.len;i++){
res.a[i]+=x.a[i]+y.a[i];
if(res.a[i]>=mod)
res.a[i+1]=1,res.a[i]-=mod;
}
if(res.a[res.len+1]>0) res.len++;
return res;
} friend M operator * (M x,M y){
M res;res.init();
for(int i=1;i<=x.len;i++)
for(int j=1;j<=y.len;j++){
res.a[i+j]+=(res.a[i+j-1]+1LL*x.a[i]*y.a[j])/mod;
res.a[i+j-1]=(res.a[i+j-1]+1LL*x.a[i]*y.a[j])%mod;
}
res.len=x.len+y.len;
while(res.len>1&&res.a[res.len]==0) res.len--;
return res;
} inline void print(void){
memcpy(b,a,sizeof(a));
printf("%d",a[len]);
for(int i=len-1;i;i--)
for(int j=1e8;j;j/=10)
printf("%d",a[i]/j),a[i]%=j;
memcpy(b,a,sizeof(b));
puts("");
} }n,m,ans,f[maxn][maxn],g[maxn][maxn]; signed main(void){
scanf("%s",s);tmp=n.len=strlen(s);n.len=tmp/9+1;
for(int i=1,j;i<=tmp;i++){
j=(tmp-i)/9;
n.a[j+1]=n.a[j+1]*10+s[i-1]-'0';
}
f[0][0].a[1]=1;f[0][0].len=1;
for(int i=1;i<=99;i++){
f[i][i].a[1]=1;f[i][i].len=1;
for(int j=0;j<i;j++)
for(int k=0;k<=j;k++)
f[i][j]=f[i][j]+f[i-1][k]*f[i-1-k][j-k];
}
int tot=0;
for(int i=0;i<=99;i++){
if(n.a[1]&1){
tot++;
if(tot==1)
for(int j=0;j<=i;j++)
g[tot][j]=f[i][j];
else
for(int j=0;j<=i;j++)
for(int k=0;k<=j;k++)
g[tot][j]=g[tot][j]+g[tot-1][k]*f[i-k][j-k];
}
int lala=0;
for(int j=n.len;j;j--){
int tmp=n.a[j];
n.a[j]=(1LL*lala*mod+tmp)/2;
lala=(1LL*lala*mod+tmp)%2;
}
}
for(int i=0;i<=99;i++) ans=ans+g[tot][i];
ans.print();
return 0;
}
By NeighThorn