P1472 [USACO2.3] 奶牛家谱 Cow Pedigrees 另解

· · 题解

这应该是一种题解区没有的做法。

想数树的形态，考虑 dp。

你会考虑在转移时进行类似合并左右子树的操作，因为将左右子树放在一起，加入根，深度恰好增加 1，节点数量总和恰好增加 1，为我们同时达成深度与点个数的目标带来了美妙的性质。

于是非常容易想到考虑 f_{i,j} 表示节点数量为 i，深度恰好为 j 的二叉树形态总数，然而你推出转移之后发现转移确实很简单但是要 \mathcal O(n^2k^2) 的时间复杂度，感觉并不够优秀啊！

虽然可以强行做前缀和优化去掉一个 k，但不妨考虑使用类似 P3830 [SHOI2012] 随机树的状态设计方式来减小复杂度。设 f_{i,j} 表示节点数量为 i，深度大于等于 j 的二叉树形态总数，考虑转移。

首先枚举 p 表示左子树贡献的节点总数，那么右子树必然贡献 i-1-p 个节点。注意到因为总深度需要大于等于 j，所以必然存在一个子树的深度大于等于 j-1（合并左右子树加上根之后，整体深度都会增加 1）。当左子树的深度大于等于 j-1 时，右子树的形态没有限制，反正深度都会大于等于 j，因此这种情况对答案的贡献为 f_{p,j-1}\times f_{i-1-p,1}。反过来如果右子树的深度大于等于 j-1，对答案的贡献就为 f_{p,1}\times f_{i-1-p,j-1}。然而你发现这样做会统计重复两边的深度都大于等于 j-1 的情况，所以你需要斥掉 f_{p,j-1\times f_{i-1-p,j-1}}。

于是整个转移就是：

f_{i,j}\gets f_{i,j}+f_{p,j-1}\times f_{i-1-p,1}+f_{p,1}\times f_{i-1-p,j-1}-f_{p,j-1\times f_{i-1-p,j-1}}

根据定义，初值即为 f_{1,1}=1,f_{3,1}=f_{3,2}=1，答案为 f_{n,k}-f_{n,k+1}。

直接朴素实现即可，复杂度 \mathcal O(n^2k)。注意减法取模，f_{i,1}\gets f_{i,2} 等实现细节。

实现：

int n,k;
int dp[210][110];
const int M=9901;
int main(){
    cin>>n>>k;
    dp[1][1]=1,dp[3][1]=dp[3][2]=1;
    fr1(i,4,n){//其实都可以只枚举奇数，但是是常数优化就无所谓了
        fr1(j,2,k+1){//因为深度为0时不合法所以从2开始枚举深度
            fr1(p,1,i-2){
                dp[i][j]+=((dp[p][j-1]*dp[i-1-p][1]%M+dp[p][1]*dp[i-1-p][j-1]%M)%M-dp[p][j-1]*dp[i-1-p][j-1]%M+M)%M;
                dp[i][j]%=M;
            }
        }
        dp[i][1]=dp[i][2];//但在最后必须记得特意给dp[i][1]赋dp[i][2]的值，后面转移可能会用到dp[i][1]
    }
    cout<<(dp[n][k]-dp[n][k+1]+M)%M<<endl;
    ET;
}

AC 记录