TediousLee

Created by LXC on Mon Jan 15 11:37:16 2024

https://codeforces.com/problemset/problem/1369/D

ranting: 1900

tag: dp, graphs, greedy, math, trees

problem

首先，我们定义 RDB 为一棵具有特殊性质的树，它有一个级别 $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\cdot 10^6$

感谢 @_Wolverine 提供的翻译

solution

通过找规律发现，一颗n阶的树，可以表示为1个顶点包含两颗n-2阶的子树和一颗n-1阶的子树。

设$f_i$为i阶的树的黄色节点个数。一个明显的想法就是区分根是不是黄色节点。当根非黄色节点，那么i阶树黄色节点个数为$2f_{i-2}+f_{i-1}$；当根为黄色节点，它的三个儿子节点也必须为黄色，那么i阶树黄色节点个数为$f_{i-2}+4f_{i-2}+4f_{i-3}+4$；

状态转移很明显就是$f_{i} = max (2f_{i-2}+f_{i-1}, f_{i-2}+4f_{i-2}+4f_{i-3}+4), f_{1} = f_2 = 0, f_3 = f_4 = 4$

但是存在一个问题就是两个数x和y在取模后求二者最大值，会出现错误。但是这里直接取模后再求最大值可以通过本题，说明这个概率很小？

另一种不涉及求最大值的做法。

一颗n阶的树，可以表示为1个顶点包含两颗n-2阶的子树和一颗n-1阶的子树。
如果n-2阶的根是绿的，n-1阶的根也是绿的。n阶的树就可以多出一个爪形，多出4个可以变黄的节点，因而n阶树树根变黄。

我们看1阶树，2阶树都是0，根没有变黄。3阶树根变黄了，4阶树根可以是绿的。5阶树也可以是绿的，规律就是黄色根是以三为周期的。

所以状态转移$f_{i} = f_{i-1} + 2f_{i-2} + (i%3==0?0:4)$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 2000005
#define MOD 1000000007
using namespace std;

ll f[N];

void sol() {
    int n;
    cin >> n;
    cout << f[n] << "\n";
}

int main() {
    // f[1] = f[2] = 0;
    // f[3] = f[4] = 4;
    // for (int i = 5; i < N; i++) {
    //     f[i] = max((f[i - 1] + f[i - 2] * 2) % MOD,
    //                (f[i - 2] + f[i - 3] * 4 + f[i - 4] * 4 + 4) % MOD);
    // }
    f[1] = f[2] = 0;
    f[3] = f[4] = 4;
    for (int i = 5; i < N; i++) {
        f[i] = f[i - 1] + f[i - 2] * 2 + (i % 3 == 0 ? 4 : 0);
        f[i] %= MOD;
    }
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}