自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 21:30:37，当前版本为作者最后更新于2020-05-27 14:40:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道令人谔谔的数学题（？

如果我们记 $c_i$ 为大小为 $i$ 的不同二叉树的个数，则有

即，去掉根之后考虑左右点的个数。

随便打个表就知道 $\sum\limits_{i=1}^{18}c_i>5\times 10^8$，只需预处理 $c_1,\cdots,c_{18}$ 即可。

我们首先对输入的 $x$ 作一些处理，改为求大小为 $n$ 的树中序号第 $x$ 个。

这一步处理很好写：

int n=1;while(x>c[n]) {x-=c[n];++n;}

之后考虑实现 void print(ll x,int n)。

按照题目要求，编号按左子树排序，相等则按右子树排序。

而树先按大小排序，因此我们可以先计算出左子树和右子树的大小，以及在这个大小下要求的树是第几个。

这部分的代码：

int l=0;while(x>c[l]*c[n-1-l]) {x-=c[l]*c[n-1-l];++l;}int r=n-1-l;

接下来，如果用 $(x,y)$ 来表示左子树编号为 $x$，右子树编号为 $y$ 的二叉树，则其排序如下：

$(1,1),(1,2),(1,3),\cdots,(1,c_r),(2,1),(2,2),\cdots,(c_l,c_r)$

不难发现，其中第 $x$ 个即为 $\left(\left\lfloor\dfrac{x-1}{c_r}\right\rfloor+1,(x-1)\mod c_r+1\right)$。

于是特判 $l,r$ 是否为 $0$ 后，分别递归下去即可。

复杂度我不会算，反正常数级别。

$\texttt{code:}$

void print(ll x,int n)
{
	int l=0;while(x>c[l]*c[n-1-l]) {x-=c[l]*c[n-1-l];++l;}int r=n-1-l;
	if(l) {putchar('(');print((x-1)/c[r]+1,l);putchar(')');}
	putchar('X');
	if(r) {putchar('(');print((x-1)%c[r]+1,r);putchar(')');}
}
int main()
{
	/* prework for c[i] */
	while(true)
	{
		ll x=rd();
		if(!x) break;
		int n=1;while(x>c[n]) {x-=c[n];++n;}
		print(x,n);
		putchar('\n');
	}
	return 0;
}