题目大意

题意

分析

考虑 dp[i][j]dp[i][j] 表示 有 ii 个节点深度为 jj 的二叉树的个数

如何转移呢？

枚举左子树的结点个数,由于要保证整棵树的深度为 jj 且左右深度相差至多为 11 ,那么左子树深度可取 j−1,j−2j-1 , j - 2

转移方程为

1
2
3
4
5
6
7
8
9
f[0][0]= 1;
for(int i = 1;i <= 2000;i++)
    for(int j = 1;j <=min(i,19LL);j++){
        for(int k = 0;k < i;k++){
            f[i][j] = (f[i][j] + f[k][j-1]*f[i-1-k][j-1])%mod;
            f[i][j] = (f[i][j] + f[k][j-2]*f[i-1-k][j-1])%mod;
            f[i][j] = (f[i][j] + f[k][j-1]*f[i-1-k][j-2])%mod;
        }
    }

时间复杂度为O(n2logn)O(n^{2} log^n)

Code

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
int n;
int f[2005][20];
void solve(){
    cin>>n;
    int res = 0;
    for(int i = 1;i <=19;i++) {
        res = (res + f[n][i])%mod;
    }
    cout << res << endl;
}
signed main()
{
    _nt;
    f[0][0]= 1;
    for(int i = 1;i <= 2000;i++)
        for(int j = 1;j <=min(i,19LL);j++){
            for(int k = 0;k < i;k++){
                f[i][j] = (f[i][j] + f[k][j-1]*f[i-1-k][j-1])%mod;
                f[i][j] = (f[i][j] + f[k][j-2]*f[i-1-k][j-1])%mod;
                f[i][j] = (f[i][j] + f[k][j-1]*f[i-1-k][j-2])%mod;
            }
        }
    int t;cin>>t;
    while(t--) solve();
    return 0;
}