Codeforces Round #652(Div.2) D. TediousLee 상세 문제해결(DP)⭐⭐⭐

F i r s t S o l u t i o n First Solution FirstSolution
끊임없이 흩어지는 이런 구조.역방향 사고보다 n항을 하나의 뿌리 노드 +2개 n-1항 +1개 n-2항으로 연결한다.dp[i]가 i항의 답안을 표시하면 dp[1]=dp[2]=0, dp[3]=1;그럼 n항의 답은 2번 n-1항 +1번 n-2항의 답이 더해지는 건가요?분명히 아니다. 왜냐하면 너는 아직 뿌리 노드를 고려하지 않았기 때문이다. 만약 이 뿌리 노드를 사용하려면, 너는 앞의 두 가지 뿌리 노드를 사용해야 한다. 전제 조건은 그들의 뿌리 노드가 아직 염색되지 않았다는 것이다.ans[i]를 i항의 발톱 수량으로 설정합니다.분명히 ans[1]와 ans[2]의 뿌리 노드가 염색되지 않았기 때문에 ans[3]는 앞의 두 가지 뿌리 노드와 함께 염색하여 1의 공헌을 할 수 있다.분명히 ans[4]와 ans[5]는 이미 염색된 ans[3]를 이용할 수 없다.ans[6]는 앞의 두 가지를 이용할 수 있기 때문에 답이 나온다.ans[i]=2*ans[i-2]+ans[i-1]+(i%3==0)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 2000005
#define rep(n) for(int i=1;i<=n;i++)
#define rall(x) for(int i=(x).size()-1;i>=0;i--)
#define all(x) for(int i=0;i<(x).size();i++)
int a[MAXN];
int b[MAXN];
ll ans[MAXN];
const long long mod=1000000007;
int main()
{
    int t;
    cin>>t;
    for(int i=3;i<=2000000;i++)
        ans[i]=(2ll*ans[i-2]+ans[i-1]+(i%3==0))%mod;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<4ll*ans[n]%mod<<endl;
    }
}

S e c o n d S o l u t i o n Second Solution SecondSolution
또 다른 방법은 제목의 결점에 대해 세 가지 상태를 나누는 것이다.첫 번째 상태는 단일 노드입니다.두 번째 상태는 하위 노드를 가진 단일 노드이다.세 번째 상태는 세 개의 하위 노드를 가진 단일 노드다.dp[i]가 제i차에 새로 생성된 결점을 기록합니다.그렇다면,

dp[1]=1
dp[i]=2*dp[i-1]+dp[i-2]

현재 마지막 라운드에서 성장할 때 새로 나타난 발톱의 수를 고려하면, 분명히 그 염색은 그들의 모노드와 겹칠 것이다. 그러나 우리는 서브노드 부분을 골라 염색하기를 원한다.ans[n]=dp[n%3+3\*\j](n%3+3*j<=n), j는 자연수를 얻을 수 있습니다.접두사와 답안을 유지하면 된다.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 2000005
#define rep(n) for(int i=1;i<=n;i++)
#define rall(x) for(int i=(x).size()-1;i>=0;i--)
#define all(x) for(int i=0;i<(x).size();i++)
int a[MAXN];
int b[MAXN];
ll dp[MAXN];
ll cnt[MAXN];
const long long mod=1000000007;
int main()
{
    int t;
    cin>>t;
    dp[1]=dp[2]=1;
    for(int i=3;i<=2000000;i++)
    {
        dp[i]=(2ll*dp[i-2]+dp[i-1])%mod;
        cnt[i]=(cnt[i-3]+dp[i-2])%mod;
    }
    while(t--)
    {
        int n;
        cin>>n;
        cout<<4ll*cnt[n]%mod<<endl;
    }
}