CF1369D TediousLee 题解

题意：

首先，我们定义 RDB 为一棵具有特殊性质的树，它有一个级别 $\mathtt{level}$。

一个级别为 $1$ 的 RDB 是一个单独的节点。

接着，对于所有 $i>1$，级别为 $i$ 的 RDB 的构成方法如下。

先求出级别为 $i-1$ 的 RDB，然后对于该 RDB 中的每个节点 $x$。

如果 $x$ 没有孩子，那么给他加上一个孩子。

如果 $x$ 只有一个孩子，那么给他加上两个孩子。

如果 $x$ 已经有了超过一个孩子，那么我们跳过节点 $x$。

以下是 $1\le n \le 3$ 的所有 RDB

接下来，我们定义一个 claw （见下图），它也是一棵具有特殊性质的树，并且将节点 $1$ 称为这个 claw 的中心，其他的称为底部节点。

现在，给出一个级别为 $n$ 的 RDB，初始时他上面的所有节点都为绿色，你可以进行一些操作。
对于每次操作，你需要在给出的 RDB 中找到一个 claw，满足所有底部节点在 RDB 中都是中心节点的儿子，且这四个节点在 RDB 中都是绿色。然后将这四个节点染为黄色。
问最多可以将多少个节点染成黄色。

输入格式：

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

接下来 $T$ 行，每行一个正整数 $n$，表示有一棵级别为 $n$ 的 RDB。

输出格式：

输出有 $n$ 行，每行一个整数，对应每组数据的答案。

这个答案可能很大，所以输出它对 $10^9+7$ 取模后的结果。

说明与提示

$1\le T\le 10^4,~1\le n \le 2\times 10^6$

设 $f_i$ 表示 $\mathtt{level}$ 为 $i$ 的树的最大涂色数，则有

$f_i = f_{i-1} + 2f_{i-2} + [3 \mid i]\times 4$

~~正确性显然吗我不知道~~，但是注意到不是 $3$ 的倍数时乱涂最上面的不优，所以是对的。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9+7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e6+15))

int Q,n,a[N],f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> Q;
    for(int i=1; i<=Q; i++) { cin >> a[i]; up(n, a[i]); }
    f[0] = f[1] = f[2] = 0; f[3] = 4;
    for(int i=4; i<=n; i++)
    {
        f[i] = ( f[i-1] + 2 * f[i-2] % mod ) % mod;
        if(i % 3 == 0) (f[i] += 4) %= mod;
    }
    for(int i=1; i<=Q; i++) cout << f[a[i]] << '\n';
    return 0;
}