CF1237E 【Balanced Binary Search Trees】

神仙题

(CF1237E ~Balanced~ Binary ~Search ~Trees)

题意：

需要求出有多少棵点数为(n(nle 10^6))点权为({1,2,...,n})的二叉搜索树满足：

(1):) 除了最下面一层外，所有层都是满的；

(2):) 对于每个点，如果它有左儿子，那么左儿子的点权和它的奇偶性不同；如果它有右儿子，那么右儿子的点权和它的奇偶性相同。

答案对(998244353)取模

(rm Sol:)

可以发现定义(1)即这棵树是一个满二叉树，于是对于根节点，有除去其之后仍然有其为一颗满二叉树

设满足定义(2)的满二叉树为完美树，则可以发现由于原树为一棵二叉查找树，于是其最右边的点一定为(n)，所以有根的奇偶性与(n)的奇偶性相同

不难看出两个性质：

(1):) 一棵完美树的子树仍然是完美树

(2):) 由于权值为(1-n)，所以这棵二叉搜索树的中序遍历为(1-n)，每棵子树则可以对应成为一个区间

考虑假设某一个数(x)作为根，此时有(x)的奇偶性与(n)相同，则其左子树的区间可以表示为([1,x-1])，右子树区间则可以表示为([x+1,n])，且有左子树大小为(x-1)，右子树大小为(n-x)，因为(n)的奇偶性和(x)相同，所以(n-x)必然为偶数，且(x-1)的奇偶性与(x)相反，由于左子树仍然是一棵完美树，所以再使用上述结论可以得到：

一颗完美树满足其左子树根的奇偶性与子树大小相同，而右子树大小为偶数

接下来由于二叉搜索树只关心相对的大小关系且其某一个子树可以被表示成为一个区间([l,r])，所以我们使用([1,r-l+1])对应替换此树所有节点对于答案没有影响，容易发现假设其原先为一棵完美树则替换后仍然是一颗完美树

所以问题与原树对应的区间编号无关而之和此树大小有关

接下来考虑将两颗完美树合并成为一颗大完美树以及其合法性，按照前面的条件我们可以得到合并之后的树为完美树当且仅当：(1.)合并之后满足原树为满二叉树，(2.)右子树大小为偶数

我们可以手玩得到：大小为(1,3,4,5)的完美树形态如下：

(size=1:quad 1)

(size=2:quad 2.leftto 1)

(size=3:) 不存在合法

(size=4:)为样例

(size=5:)仅存在一个，为：

(3.leftto 2,2.leftto1,3.rightto 5,5.left to 4)

可以观察到除去(size=1)之外的所有完美树高度均(>1)且不为满二叉树

由于 性质(1) 我们知道对于一个大小(>5)的完美树，有其最底层仍然是一棵完美树，换而言之其除去根之后必然是不满的，所以我们可以得出一个可怕的结论：

将两颗完美树合并成一棵大小(>5)的完美树当且仅当(1.):) 其左右子树为完美树且高度相同，(2):)右子树大小为偶数

现在我们可以设计一个非常粗略的(dp)了，令(dp_{i,j})表示大小为(i)的完美树高度为(j)的时候的方案数，然后利用这个东西转移，这样是(O(nlog n))的做法

仔细思考会发现一个更可怕的东西

我们知道前(5)项的高度和方案数(前为高度，后为方案数)大致如此：

((1,1),(2,(-,-),(3,1))

注意到右子树的大小仅能是(2)和(4)

对于右子树(2)而言唯一的合并是左(2)右(2)，合并得到(5)

对于右子树(4)而言唯一的合并是左(4/5)右(4)，合并得到大小为(9/10)的完美树，高度为(4)

那么这样对于大小为(6-8)的树其均不具有完美树，于是接下来可以用的大小仅有(9/10)

类似合并可以发现(9/10)仅能通过合并得到(20/21)，然后可行的为(41/42)...可以发现合法的树均只有(1)种

于是只需要拿(4/5)作为初值递推下去即可，复杂度(O(log n))

时间(3s)和(n)只有(10^6)应该是为了放其他大常数非正解做法过....

(Code:)

#include<bits/stdc++.h>
using namespace std ;
#define rep( i,s,t ) for( register int i = s; i <= t; ++ i )
#define re register
int gi() {
    char cc = getchar() ; int cn = 0,flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0',cc = getchar() ;
    return cn * flus ;
}
int n ; 
signed main()
{
    n = gi() ; 
    if( n == 1 || n == 2 ) puts("1") ;
    else {
        int x = 4,y = 5 ; 
        while( max( x,y ) < n ) {
            int ux = x,uy = y ;
            if( ux & 1 ) x = ux + uy + 1,y = uy + uy + 1 ;
            else x = ux + uy + 1,y = ux + ux + 1 ; 
            if( x > y ) swap( x,y ) ;
        }
        if( x == n || y == n ) puts("1") ;
        else puts("0") ;
    }
    return 0 ;
}