D. TediousLee （找规律、推导）

电玩女神 2021-07-17 02:28 456阅读 0赞

[题目][Link 1]

一层层推导下去很容易发现规律，a\[i\]=2\*a\[i-2\]+a\[i-1\]，看下面这张图，标着的序号代表以这个顶点为根的整颗子树所对应的阶次。6由两个4一个5组成，5由两个3一个4组成。那涂色得到的答案不就是上方的公式吗？但答案去是不对的，这还忽略了一个claw树，当达到6阶层时按照如下涂红色的去取会发现还多了一个claw，就是最上面的那个4个点，那么我们现在只要找到什么时候还要给答案加一个claw即可，当我们要求第i阶层时会发现只有当i-1 与 i-2最上面的点都是不取时可以多构成一个claw，然后相应的第i第阶层最上面的点变成取用状态，那我们只需额外去记录前两个的阶层最上面点是空还是不空的状态不断推导即可，为了方便直接开一个数组0代表空着4代表已取用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]Code:

#include<iostream>
    #include<cmath>
    #include<iomanip>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max = 2e6 + 5;	
    const ll Mod = 1e9 + 7;
    ll  ans[Max] = { 0,0,0,4,4};
    int d[Max] = {  0,0,0,1,0,0 };
    
    int main()
    { 
    	for (int i = 5;i <= Max-1;i++)
    	{ 
    		ans[i] = ans[i - 2] * ll(2) + ans[i - 1];
    		if (d[i - 1] == 0 && d[i - 2] == 0)d[i] += 4;
    		ans[i] += d[i];
    		ans[i] %= Mod;
    	}
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		cout << ans[n] << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1369/problem/D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/7c4fc1a1ff1a4e97b1b97a4bd0fe2c3b.png