题目链接：https://codeforces.ml/contest/1369/problem/D
题意：初始为一个点 每个点如果没有儿子 就+一个儿子 如果有儿子就再+2个儿子
如果一个点有3个儿子就不会再改变 每一步的时候每个不满足的点都会改变 问不重复最多找几个爪子
思路：看到t的范围和n的范围 肯定是预处理一个答案 然后O（1）查询 考虑到当前的答案和上一个有关
那么就是递推来求解了 通过画图来确定每当i%3 ==0 的时候能多一个不重复的爪子 而旁边的生成儿子有2个
推得dp[i]=dp[i-1]+dp[i-2]*2 如果i%3==0 就再+4 这样可以确保儿子的时候也+过4 因为之前的dp已经走过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define pb push_back 5 const int maxn=2e6+10; 6 const int mod=1e9+7; 7 ll dp[maxn]; 8 9 int main() 10 { 11 ios::sync_with_stdio(false); 12 cin.tie(0); 13 int t; 14 dp[1]=0; 15 dp[2]=0; 16 for(int i=3;i<maxn;i++) 17 { 18 dp[i]=dp[i-1]+dp[i-2]*2; 19 if(i%3==0) 20 dp[i]+=4; 21 dp[i]%=mod; 22 } 23 cin>>t; 24 while(t--) 25 { 26 int n; 27 cin>>n; 28 cout<<dp[n]<<‘\n‘; 29 } 30 31 32 33 34 }
Codeforces Round #652 (Div. 2) D. TediousLee
原文：https://www.cnblogs.com/winfor/p/13191570.html
