166E(DP)

1つの頂点はそれぞれA,B,C,Dの四面体である.各ステップは、ある頂点から別の頂点に移動し、Dからnステップを経てDに戻る方法の数を尋ねることができる.dp[i]をiステップでDに戻る方法の数を表すとする.ステップごとに3つの可能性があり、ステップnで3^nの場合、合計メソッド数からステップn-1でDに戻るメソッド数、すなわちステップnでDに戻るメソッド数を減算します.すなわちdp[n]=3^n-dp[n-1]
 

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define LL __int64
int main()
{
    LL n,a1=0,a2=0,tot=1;
    cin>>n;
    for(int i=2;i<=n;++i)
    {
        tot=tot*3%MOD;
        a2=(tot-a1+MOD)%MOD;
        a1=a2;
    }
    printf("%I64d
",a2);
    return 0;
}