CF1369D TediousLee 题解

题目链接：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;
}