首先我们要注意到一个性质:由于根与右子树的根奇偶性相同,那么根的奇偶性与$N$相同
然后我们发现对于一个完美树,他的左右两个儿子都是完美树
也就是说,一颗完美树是由两棵完美树拼成的
注意到另一个性质:由于权值是一个排列,假设根节点为$x$,那么左子树的范围是$[1, x - 1]$,右子树为$[x + 1, n]$
由于根节点和$N$奇偶性相同,那么左子树的大小与$N$的奇偶性相反,所以右子树大小为偶数
如果子树区间为$[l, r]$,那么其实可以把它看成$[1, r - l + 1]$,所以只和子树大小有关,和子树权值无关
手玩一波小数据:
当$N=1$时,就是一个点
当$N=2$时,二为根,一为根的左子树
当$N=3/4$时为样例
当$N=5$时,可以用两个2的子树拼成
然后我们发现,能作为右子树的只有$2/4$,前五个都不是满二叉树,所以我们可以合并两颗树,当且仅当两个二叉树高度相同
发现2的高度为2,没有与之相同树高的树,所以能作为右子树的只有$4$
所以我们就有:用$4/5$可以凑出$9/10$,$9/10$又可以拼出$19/20$……
所以我们就可以用$4/5$一路递推下去,发现每次都*了$2$,所以复杂度为$O(logN)$
## $Code:$
```
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, x = 4, y = 5;
scanf("%d", &n);
if(n == 1 || n == 2) return puts("1"), 0;
while(y < n) {
if(x & 1) x = 2 * y, y = x + 1;
else x = 2 * y - 1, y = x + 1;
}
return printf("%d", (x == n || y == n)), 0;
}
```