本文共 1524 字，大约阅读时间需要 5 分钟。

题目描述：

首先，我们先假设一下是2*n的正方形，得到启发：

2*2的组成情况，和2*3的组成情况。

可以知道2*2要么全是竖着要么全是横着(有2种)  

要么是把自己的上一个切了一半儿的

每一次新增一排新的2*1，要么增加了一种(f[i-1]*1)，要么增加的是半个，就是f[i-2]

如果这半个当做两个横着来统计的话，实际上已经在前面就计算过了，包含，所以不用管，f[i-2]还是只有一种

所以f[i]=f[i-1]+f[i-2] 两种转移过来的(大概吧)

继续往下推导  

(1)3*n的只能一次增加两个  奇数除不尽

(2) 在增加两个的时候，首先，增加一个3*2的，有3种

(3)增加两个的时候忽略了这样一种情况，而这种情况是可以一直不停往前递推的，所以我们可以拿到一个式子，然后减一下就拿到通项。

就是这个丑丑的图，这种情况跨了三个，而且可以往上移，有2种，一直到往前每个地方都可以加上3个，就得到了下面的狮子

【remember】

【这种看起来是递推的， 就别硬着头皮找规律啊啊呵呵呵。。】

洛谷这个题，看着kkk的题解感觉还行

题意就是有n节点 k高度的二叉树有多少种组合方式，子树要么是2要么是0

内部实现过程还是有点玄幻。。。 （懵）

所以以后抽特王不是同期做的题就别问他了。。。-。-  丧失信心.jpg

// luogu-judger-enable-o2#include
   
    #include
    
     #include
     
      using namespace std;int t[205][205];int s[205][205];//开在外面默认是0..我的天啊(int main() {    int k,n;    cin>>n>>k;//n是结点数量  k是层数    t[0][0]=1;    s[0][0]=1;    t[1][1]=1;    s[1][1]=1;    for(int i=2; i<=k; i++) {        //i是第几层        for(int j=1; j<=n; j=j+2) {            //j是 在第i层    结点数量有几个            for(int k=1; k<=j; k=k+2) {                //k是枚举在第i层有j个结点的情况下                //左子数的结点个数, 和对应的右的个数                //t是记录的                //s就是小鱼它的所有的                t[i][j]+= (s[i-2][k]*t[i-1][j-1-k])%9901;                t[i][j]+= (t[i-1][k]*s[i-2][j-1-k])%9901;                t[i][j]+= (t[i-1][k]*t[i-1][j-1-k])%9901;                t[i][j]%= 9901;                //	printf(" i %d j %d k %d s %d t %d\n",i,j,k,s[i][j],t[i][j]);            }            s[i][j]=(s[i-1][j]+t[i][j])%9901;        }    }    cout<<(t[k][n]+9901)%9901<
     
    
   

弄好变量名字，分析好过程，边界知道，dp。。-。- 

丧失信心.jpg 好烦啊

参考：