Description：

求 $n$ 划分成二的整次幂的方案数。

$1\le n \le 10^{30}$

Solution：

一个二的次幂分解成二的次幂，一定是把他拆成两个小一的二的次幂。

设 $f[i][l][r]$ 表示把 $2^i$ 分解成最大 $2^l$ ，最小 $2^r$ 的方案数。

$\begin{align}f[i][l][r]=\sum_{k=l}^r f[i-1][l][k]\times f[i-1][k][r]\end{align}$ ，因为相同拆分算同一种方案，所以假设左边的都比右边大。

但是由于有 $f[i][l][r]=f[i-1][l-1][r-1]$ ，所以只用保存 $f[i][l][0]$ ，于是 $f[i][j]$ 表示把 $2^i$ 分解为最大为 $2^j$ 的方案数。即 $\begin{align}f[i][l][0]=\sum_{k=l}^r f[i-1][l][k]\times f[i-1][k][0]\end{align}$ ，由于前半部分要求大于 $k$ ，就整体除掉 $k$ ，即 $f[i-1][l][k]=f[i-k-1][l-k][0]$ ，于是 $f$ 转移为 $\begin{align}f[i][j]=\sum_{k=0}^jf[i-1][k]\times f[i-j-1][k-j]\end{align}$ 。

然后问题是怎么统计答案，先把 $n$ 二进制分解，设 $g[i][j]$ 表示做完了 $n$ 的二进制的前 $i$ 个一，最大数是 $2^j$ 的方案数，有转移 $\begin{align}g[i][j]=\sum_{k=0}^jg[i-1][k]\times f[w][j][k]\end{align}$ ，思路与之前相似，还是保证新产生的比之前分解的都大， $w$ 是 $i$ 这位所代表的 $2$ 的指数，先之前一样 $f[w][j][k]=f[w-k][j-k][0]$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#pragma GCC optimize(3)

using namespace std;

#define BASE 1000000000

typedef long long ll;

#define MAXN 99

struct bigint

{

	int w,a[170];

	bigint(){w = 0;memset(a,0,sizeof(a));}

	friend bigint operator + (bigint a,bigint b)

	{

		register bigint t;

		t.w = max(a.w,b.w);

		for(register int i = 1;i <= t.w;++i)

		{

			t.a[i] += a.a[i] + b.a[i];

			if(t.a[i] >= BASE)

			{

				t.a[i + 1] = 1;

				t.a[i] -= BASE;

			}

		}

		if(t.a[t.w + 1] > 0)++t.w;

		return t;

	}

	friend bigint operator * (bigint a,bigint b)

	{

		register bigint t;

		for(register int i = 1;i <= a.w;++i)

		{

			for(register int j = 1;j <= b.w;++j)

			{

				t.a[i + j] += ((ll)t.a[i + j - 1] + (ll)a.a[i] * (ll)b.a[j]) / BASE;

				t.a[i + j - 1] = ((ll)t.a[i + j - 1] + (ll)a.a[i] * (ll)b.a[j]) % BASE;

			}

		}

		for(t.w = a.w + b.w;t.w > 1 && t.a[t.w] == 0;--t.w);

		return t;

	}

}f[MAXN + 5][MAXN + 5],ans,n,s[MAXN + 5],g[MAXN + 5][MAXN + 5];

char c[170];

int main()

{

	scanf("%s",c + 1);

	register int l = strlen(c + 1);

	n.w = l / 9 + 1;

	for(register int i = 1;i <= l;++i)

	{

		register int j = (l - i) / 9;

		n.a[j + 1] = n.a[j + 1] * 10 + c[i] - '0';

	}

	f[0][0].w = f[0][0].a[1] = 1;

	for(register int i = 1;i <= MAXN;++i)

	{

		for(register int j = 0;j < i;++j)

		{

			for(register int k = 0;k <= j;++k)

			{

				f[i][j] = f[i][j] + f[i - 1][k] * f[i - 1 - k][j - k];

			}

		}

		f[i][i].w = f[i][i].a[1] = 1;

	}

	register int tot = 0;

	for(register int i = 0;i <= MAXN;++i)

	{

		if(n.a[1] & 1)

		{

			++tot;

			if(tot == 1)

			{

				for(register int j = 0;j <= i;++j)g[1][j] = f[i][j];

			}

			else

			{

				for(register int j = 0;j <= i;++j)

				{

					for(register int k = 0;k <= j;++k)

					{

						g[tot][j] = g[tot][j] + g[tot - 1][k] * f[i - k][j - k];

					}

				}

			}

		}

		register int r = 0;

		for(register int j = n.w;j >= 1;--j)

		{

			register int t = n.a[j];

			n.a[j] = ((ll)r * BASE + t) / 2;

			r = ((ll)r * BASE + t) % 2;

		}

	}

	for(register int i = 0;i <= MAXN;++i)ans = ans + g[tot][i];

	printf("%d",ans.a[ans.w]);

	for(register int i = ans.w - 1;i;i--)

	{

		for(register int j = BASE / 10;j >= 1;j /= 10)

		{

			putchar('0' + (ans.a[i] / j));

			ans.a[i] %= j;

		}

	}

	puts("");

	return 0;

}