好难啊 QAQ

Problem

给定一个确定的深度 k 和点数 n
问有多少个不同的二叉树（左子树和右子树其中一个不同即该方案不同，每个结点度数必须为 0 或 2）

Solution

一开始考虑拉一条链下来
然后进行大讨论
然后搞了三个函数互相调用
错了之后发现可以删掉一个函数
然后发现变成了下面这样：

$f_{i,j}$ 深度一定为 $i$，结点数为 $j$ 的方案数

$S_{i,j}$ 深度 $\leq i$，结点数为 $j$ 的方案数

显然有：$S_{i,j}=\sum_{x=1}^i f_{x,j}$

由此对子树进行讨论，令其中一个子树深度达到 i - 1 即可。由于可以交换左右子树，因此方案数 *2。

那么问题来了，如果左右子树完全相同，方案数不能重复统计。

那么考虑如果左子树深度计算为 i -1，右子树深度计算同样为 i -1，此时交换左右子树会导致方案重复统计（考虑你枚举点数的循环，你已经计算过了交换左右子树的情况，或者你压根不会计算（完全二叉树））。

因此此时就不用交换左右子树了。

所以有：$$f_{i,j}=\sum_{y=1}^{j-2} f_{i-1,j-1-y}*(f_{i-1,y}+2*S_{i-2,y})$$

初始化：$f_{1,1}=1$。

Code

#include<bits/stdc++.h>
#define MOD (9901)
using namespace std;

const int N=202;
int f[N][N], f3[N][N];
int dp(int, int);
int S(int, int);
int dp(int x, int y) {
    if(x==1) return y==1;
    if(y<x) return 0;
    if(f[x][y]!=-1) return f[x][y];
    f[x][y]=0;
    for(int i=1;i<y-1;i++)
        f[x][y]=(f[x][y]+dp(x-1, y-i-1)*(S(x-2, i)*2+dp(x-1, i)))%MOD;
    return f[x][y];
}
int S(int x, int y) {
    if(x<=0) return 0;
    if(f3[x][y]!=-1) return f3[x][y];
    f3[x][y]=0;
    for(int i=1;i<=x;i++) f3[x][y]=(f3[x][y]+dp(i, y))%MOD;
    return f3[x][y];
}

int main() {
    freopen("nocows.in","r",stdin);
    freopen("nocows.out","w",stdout);
    ios::sync_with_stdio(false), cin.tie(0);
    int n, k;
    cin>>n>>k;
    memset(f, -1, sizeof(f)), memset(f3, -1, sizeof(f3));
    cout<<dp(k, n)<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-usaco-nocows.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆