题解 P1814 【数的序号】

· · 题解

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

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

c_0=1,c_n=\sum\limits_{i=0}^{n-1}c_ic_{n-1-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;
}