【Codeforces 1369D】TediousLee

题目链接

点我呀

翻译

高度为 \(i+1\) 的一棵 \(RDC\) 树可以由高度为 \(i\) 的一棵 \(RDC\) 树通过这样的规则构造出来:

在高度为 \(i\) 的 \(RDC\) 中，对于只有一个孩子的节点，加上两个孩子节点，没有孩子的节点加上一个节点。

问你高度为 \(h\) 的 \(RDC\) 树有多少个互不重叠的爪型的节点。

题解

递推题。

动手画一下的话，会发现高度为 \(h\) 的 \(RDC\) 树，总是由两个高度为 \(h-2\) 的 \(RDC\) 树和一个高度为 \(h-1\) 的 \(RDC\) 以及一个根节点

构成的。

选取爪型的时候，应该尽量让选择的爪的根节点在子树下方，这样整个树的根节点就能跟三个子树的根节点再形成一个爪了。

所以思路就是，设置一个 \(ans[N]\) 表示高度为 \(h\) 的 \(RDC\) 树能有多少个爪，以及选出的爪中有没有选树的根节点。

然后，\(ans[i] = ans[i-2]*2+ans[i-1]+can\), 其中如果高度为 \(i-2\) 和 \(i-1\) 的 \(RDC\) 树都没有选根节点作为爪的根的话，

则 \(can=1\)，否则 \(can = 0\)。

最后输入 \(n\), 直接输出 \(ans[n]*4\) 即可。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2e6;
const LL MOD = 1e9+7;

LL ans[N+10];
bool used[N+10];

int main()
{
    ans[1] = 0;ans[2] = 0;
    for (int i = 3;i <= N; i++){
        if (!used[i-1] && !used[i-2]){
            ans[i] = ans[i-2]*2%MOD + ans[i-1] + 1;
            ans[i] %= MOD;
            used[i] = true;
        }else{
            ans[i] = ans[i-2]*2%MOD + ans[i-1];
            ans[i] %= MOD;
        }
    }
    int T;
    scanf("%d",&T);
    while (T--){
        int n;
        scanf("%d",&n);
        printf("%lld\n",ans[n]*4%MOD);
    }
    return 0;
}