\(\mathcal{Description}\)

Link.

定义棵点权为 \(1\sim n\) 的二叉搜索树 \(T\) 是好树，当且仅当：

除去最深的所有叶子后，\(T\) 是满的；
对于 \(T\) 中任意结点 \(r\)，若 \(r\) 存在左儿子 \(u\)，则 \(r\not\equiv u\pmod2\)；
若 \(r\) 存在右儿子 \(v\)，则 \(r\equiv v\pmod2\)；

给定 \(n\)，求好树数量。答案对 \(998244353\) 取模。

\(\require{cancel} \cancel{n\le10^6}~n\le10^{10^6}\)。

\(\mathcal{Solution}\)

分析一下含有 \(n\) 个结点的好树的性质：

好树的子树是好树。
树根 \(r\) 有 \(r\equiv n\pmod2\)。因为从根一直走右儿子奇偶性不变。
当 \(n>1\)，好树不满。若满，最大值和次大值必为右儿子-父亲关系，不满足定义。
由 3.，当 \(n>2\)，好树树根的左右子树的最大满层相同。

我们这样断言：最大满层深度为 \(h\) 的好树存在且仅存在两个，且它们的大小之差为 \(1\)。

给出证明。设含 \(n\) 个结点的好树有 \(f(n)\) 个，那么 \(f(1)=f(2)=1\)，它们最大满层深度均为 \(1\)。归纳 \(n>2\) 的情形：

取一棵含 \(n\) 个点的好树 \(T\)，其树根为 \(r\)，左右儿子为 \(u,v\)，最大满层深度为 \(h\)。

由性质 1.，子树 \(u\) 和子树 \(v\) 是好树；

由性质 3.，子树 \(u\) 和子树 \(v\) 不满；

由假设，\(T\) 为好树，子树 \(u\) 和子树 \(v\) 最大满层相同。那么可以对这两棵子树进行归纳。

若 \(2\not\mid n\)，

可知子树 \(u\)，子树 \(v\) 大小奇偶性相同，由性质 4. 与归纳假设，子树 \(u\) 和子树 \(v\) 的大小相等，且均为偶数，继而有

\[ f(n)=f^2\left(\frac{n-1}{2}\right)~~~~(n=4k+1,k\in\mathbb N^*).
\]
若 \(2\mid n\)，

可知子树 \(u\)，子树 \(v\) 大小奇偶性不同，由归纳假设，子树 \(u\) 和子树 \(v\) 大小相差 \(1\)，继而有

\[ f(n)=f\left(\frac{n}{2}-1\right)f\left(\frac{n}{2}\right).
\]

（注意左右子树不能交换，所以只有一种放法。）

综上，不难发现 \(f(n)\) 在归纳条件下至多为 \(1\)。我们只需要证明存在某对使得 \(T\) 最大满层深度为 \(h\) 的 \(n_0\) 和 \(n_0+1\)，使得 \(f(n_0)=f(n_0+1)=1\)。

构造，设当 \(h'=h-1\) 时已有 \(f(n_0')=f(n_0'+1)=1\)，那么

若 \(2\mid n_0\)，有 \(f(2n_0)=f(2n_0+1)=1\)；
若 \(2\not\mid n_0\)，有 \(f(2n_0+2)=f(2n_0+1)=1\)。

综上，归纳可行，原命题成立。 \(\square\)

利用最后一步的构造方法，我们可以 \(\mathcal O(\log n)\) 地求得所有 \(n_0\le n,f(n_0)=1\) 的 \(n_0\)。当然也能以同样复杂度判断 \(f(n)\) 是否为 \(1\)。

正确解题姿势：写 \(\mathcal O(n^2)\) DP，打表秒出规律。

\(\mathcal{Code}\)

Subtask12 即打表代码。

/*~Rainybunny~*/

#include <bits/stdc++.h>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

const int MAXN = 5e6;

int n, M;

bool ans[MAXN + 5];

inline int imin( const int u, const int v ) { return u < v ? u : v; }

inline int imax( const int u, const int v ) { return u < v ? v : u; }

inline int mul( const int u, const int v ) { return 1ll * u * v % M; }

inline void addeq( int& u, const int v ) { ( u += v ) >= M && ( u -= M ); }

namespace Subtask12 {

int bitw[MAXN + 5], f[MAXN + 5];

inline void main() {

    f[0] = f[1] = 1, bitw[0] = -1;

    rep ( i, 2, n ) {

        bitw[i] = bitw[i >> 1] + 1;

        rep ( j, 1, i ) {

            if ( ( i & 1 ) == ( j & 1 )

              && imin( bitw[j], bitw[i - j + 1] ) + 1 >= bitw[i]

              && imax( bitw[j - 1], bitw[i - j] ) + 1 == bitw[i] ) {

//                  printf( "(%d,%d)->%d\n", j - 1, i - j, i );

                addeq( f[i], mul( f[j - 1], f[i - j] ) );

            }

        }

        if ( f[i] ) assert( f[i] == 1 ), printf( "%d\n", i );

    }

}

} // namespace Subtask12.

int main() {

    freopen( "tree.in", "r", stdin );

    freopen( "tree.out", "w", stdout );

    scanf( "%d %d", &n, &M );

    for ( int i = 2, op = 1; i <= MAXN + 1; ) {

        ans[i] = ans[i - 1] = true;

        i = i << 1 | op, op ^= 1;

    }

    putchar( ans[n] ^ '0' ), putchar( '\n' );

    return 0;

}

巴特西

Solution -「CF 1237E」Balanced Binary Search Trees

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章