[BZOJ]BST again

偏执的太偏执、 2021-09-30 00:32 152阅读 0赞

## Description ##

求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模）

## Input ##

第一行一个整数T，表示数据组数。

以下T行，每行2个整数n和h。

## Output ##

共T行，每行一个整数表示答案（对1000000007取模）

## Sample Input ##

2  
2 1  
3 2

## Sample Output ##

2  
4

## HINT ##

对于100%的数据，1<=n<=600,0<=h<=600,1<=T<=10

## Source ##

不会做，抄的题解，还被卡常。设$f\[i\]\[j\]$表示放$i$个节点深度小于等于$j$的个数，然后我们会有这么一个想法：已知两棵树，如何拼成一棵新的树?我们可以加一个顶点，让两棵树分别为左右子树，而深度刚好在原先的基础上加1。所以枚举最大深度小于等于$j-1$的两棵树去更新最大深度小于等于$j$的两棵树即可

代码：

1 #include<cstdio>
     2 #include<cstring>
     3 const int M=605;
     4 const int mod=1000000007;
     5 int T,f[M][M];
     6 inline int dfs(int x,int y)
     7 {
     8     if(x==0) return 1;
     9     if(y==0) return (x==1);
    10     if(~f[x][y]) return f[x][y];
    11     long long ans=0;
    12     for(int i=1;i<=x;i++) ans=(ans+(long long)dfs(i-1,y-1)*(long long)dfs(x-i,y-1)%mod)%mod;
    13     return f[x][y]=ans;
    14 }
    15 int main()
    16 {
    17     scanf("%d",&T);
    18     memset(f,-1,sizeof(f));
    19     while(T--)
    20     {
    21         int x,y; scanf("%d%d",&x,&y);
    22         printf("%d\n",(dfs(x,y)-(y?dfs(x,y-1):0)+mod)%mod);
    23     }
    24     return 0;
    25 }

转载于:https://www.cnblogs.com/Slrslr/p/9589970.html

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 Fibonacci again and again（求sg函数）

Problem Description 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生，它是这样定义的： F(1)=1; F(2)

﹏ヽ暗。殇╰゛Y/ 2024年02月17日 22:22/ 0 赞/ 66 阅读

相关 Fibonacci Again

Fibonacci Again Time Limit: 1000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述 There

「爱情、让人受尽委屈。」/ 2022年08月10日 05:50/ 0 赞/ 167 阅读

相关 Fractions Again?!

[Fractions Again?!][Fractions Again] <table> <tbody> <tr> <td><strong>Time Lim

向右看齐/ 2022年08月03日 16:58/ 0 赞/ 195 阅读

相关 Fibonacci Again

Problem Description： There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11,

向右看齐/ 2022年05月29日 07:10/ 0 赞/ 187 阅读

相关 HDU 1848 Fibonacci again and again【博弈SG】

Problem Description 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生，它是这样定义的： F(1)=1; F(2

矫情吗；*/ 2022年01月06日 07:27/ 0 赞/ 223 阅读

相关 GCD Again

<table> <tbody> <tr> <td> <h1>GCD Again</h1> </td> </tr> <tr> <td>Tim

忘是亡心i/ 2021年12月24日 17:21/ 0 赞/ 260 阅读

相关 begin again

今天，很神奇，和妈妈共用一个耳机一起散步听了妈妈的歌单妈妈应该是没有看过 begin again 的神奇神奇转载于:https://www.cnblogs.co

叁歲伎倆/ 2021年11月01日 04:48/ 0 赞/ 308 阅读

相关 Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a sta

- 日理万妓/ 2021年09月30日 03:04/ 0 赞/ 235 阅读

相关 celery trying again

response = push.send() Request failed with status 400: '1011 {'code': 1011, 'mes

怼烎@/ 2021年06月24日 15:56/ 0 赞/ 373 阅读

相关 Doing Homework again

描述 Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homew

拼搏现实的明天。/ 2021年06月24日 13:58/ 0 赞/ 307 阅读