每月一题2019.7

发表于 | 分类于

集训时出的水题（每月一题越来越水）。

题面

假设这个二叉搜索树内的节点权值为$[1,n]$。

那么我们可以发现一个有趣的性质就是该二叉搜索树中的每个子树内的值域都是连续的。

所以可以设计出状态$f_{i,j,k,p}$表示值域$[i,j]$构成的红黑树的黑高度为k,根为红或黑色的情况下红黑树的种数。

每次枚举当前的红黑树的根的权值以及颜色，可以写出一个$O(n^4)$的dp:

设$f_{i,j,k,2}=f_{i,j,k,0}+f_{i,j,k,1}$

又观察到实际上没有必要枚举值域的范围，只需要知道红黑树的大小就可以进行上面的dp，那么可以省去一维状态。

又因n个节点的红黑树树高为$[\lfloor \frac{log_2 n}{2}+1\rfloor,\lfloor log_2 (n+1) \rfloor ]$，第二维的状态总数实际上只有$O(logn)$种。

那么我们就得到了一个$O(n^2logn)$的算法。

进一步观察得到的两个dp方程,还是设$f_{i,j,2}=f_{i,j,0}+f_{i,j,1}$。

这是一个卷积的形式，那么对于答案的第二维做一遍卷积dp就可以得到答案了。
复杂度$O(nlog^2 n)$，可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define rnt re int
#define re register
#define I inline int
#define V inline void
#define ll long long int
#define FOR(i,A,B) for(rnt i(A),_ed(B);i<=_ed;i++)
#define ROF(i,A,B) for(rnt i(A),_ed(B);i>=_ed;i--)
const int N=1<<19|1,mod=998244353,G=3,inv3=332748118,inv2=499122177;
I Pow(re ll t,rnt x){
    re ll s=1;
    while(x){
        if(x&1)s=s*t%mod;
        x>>=1,t=t*t%mod;
    }
    return s;
}
namespace poly{
    int lmt(1),r[N],w[N];
    V init(rnt n){
        rnt l=0;
        while(lmt<=n)lmt<<=1,++l;
        FOR(i,1,lmt-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        rnt wn=Pow(3,mod>>l);w[lmt>>1]=1;
        FOR(i,(lmt>>1)+1,lmt-1)w[i]=(ll)w[i-1]*wn%mod;
        ROF(i,(lmt>>1)-1,1)w[i]=w[i<<1];
        lmt=__builtin_ctz(lmt);
    }
    I getLen(rnt n){return 1<<(32-__builtin_clz(n));}
    V DFT(int*a,rnt l){
        static unsigned long long int tmp[N];
        rnt u(lmt-__builtin_ctz(l)),t;
        FOR(i,0,l-1)tmp[i]=a[r[i]>>u];
        for(rnt i=1;i<l;i<<=1)
            for(rnt j=0,step=i<<1;j<l;j+=step)
                FOR(k,0,i-1){
                    t=tmp[i+j+k]*w[i+k]%mod;
                    tmp[i+j+k]=tmp[j+k]+mod-t;
                    tmp[j+k]+=t;
                	
                }
        FOR(i,0,l-1)a[i]=tmp[i]%mod;
    }
    V IDFT(int*a,rnt l) {
        reverse(a+1,a+l),DFT(a,l);
        rnt bk(mod-mod/l);
        FOR(i,0,l-1)a[i]=(ll)a[i]*bk%mod;
    }
}
int n,m,ans;
int f[2][20][N],tmp[N];
V input(){cin>>n,m=31-__builtin_clz(n+1);}
V init(){poly::init(n+n+3);}
V work(){
    int l=poly::getLen(n+n+3);
    f[0][0][0]=f[1][0][1]=1;
    FOR(j,1,m){
        FOR(i,0,n)tmp[i]=(f[0][j-1][i]+f[1][j-1][i])%mod;
        poly::DFT(tmp,l);
        FOR(i,0,l-1)tmp[i]=1ll*tmp[i]*tmp[i]%mod;
        poly::IDFT(tmp,l);
        FOR(i,1,n)f[0][j][i]+=tmp[i-1];
        FOR(i,0,l-1)tmp[i]=0;
        FOR(i,0,n)tmp[i]=f[0][j][i]%mod; 
        poly::DFT(tmp,l);
        FOR(i,0,l-1)tmp[i]=1ll*tmp[i]*tmp[i]%mod;
        poly::IDFT(tmp,l);
        FOR(i,1,n)f[1][j][i]+=tmp[i-1];
        FOR(i,0,l-1)tmp[i]=0;
    }
    FOR(i,0,m)ans=(ans+f[0][i][n])%mod;
    cout<<ans;
}
int main(){
    input();
    init();
    work();
    return 0;
}