题目链接：

　　

题目：

题意：

　　给你一个三菱锥，初始时你在D点，然后你每次可以往相邻的顶点移动，问你第n步回到D点的方案数。

思路：

　　打表找规律得到的序列是0,3,6,21,60,183,546,1641,4920,14763，通过肉眼看或者oeis可以得到规律为。

　　dp计数：dp[i][j]表示在第i步时站在位置j的方案数，j的取值为[0,3]，分别表示D,A,B,C点，转移方程肯定是从其他三个点转移。

代码实现如下：

 非dp计数：

1 #include 
     
       2 #include 
      
     

dp计数代码：

1 #include 
     
       2 #include 
      
     

BM代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
          
         
        
       
      
     

三份代码跑的时间如下（忽略MLE那发，从上到下分别为BM,DP，公式）：