题目大意：

古老的汉诺塔问题是这样的:用最少的步数将N个半径互不相等的圆盘从1号柱利用2号柱全部移动到3号柱，在移动的过程中小盘要始终在大盘的上面。

现在再加上一个条件：不允许直接把盘从1号柱移动到3号柱，也不允许直接把盘从3号柱移动到1号柱。

把盘按半径从小到大用1到N编号。每种状态用N个整数表示，第i个整数表示i号盘所在的柱的编号。则N=2时的移动方案为：

(1,1)=>(2,1)=>(3,1)=>(3,2)=>(2,2)=>(1,2)=>(1,3)=>(2,3)=>(3,3)

初始状态为第0步，编程求在某步数时的状态。

思路：

如果把汉诺塔的变化打出来，那么就是这样的：

1. (1,1,1)
2. (2,1,1)
3. (3,1,1)
4. (3,2,1)
5. (2,2,1)
6. (1,2,1)
7. (1,3,1)
8. (2,3,1)
9. (3,3,1)
10. (3,3,2)
11. (2,3,2)
12. (1,3,2)
13. (1,2,2)
14. (2,2,2)
15. (3,2,2)
16. (3,1,2)
17. (2,1,2)
18. (1,1,2)
19. (1,1,3)
20. (2,1,3)
21. (3,1,3)
22. (3,2,3)
23. (2,2,3)
24. (1,2,3)
25. (1,3,3)
26. (2,3,3)
27. (3,3,3)

然后，就能发现： 

1号圆盘在移动3次中，共移动了2次；2号圆盘在移动9次中，共移动了2次；3号圆盘在移动27次中，共移动了2次。 

那么也就很容易推出：n号圆盘每移动3n次中，会移动两次！ 

那么这道题就很好做了，预处理3n3n，每次可以利用周期问题求出答案。 

时间复杂度：O(tn)，最坏950000。

 

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const char o[]={
   '1','2','3','2'}; 7 int t,n,m,num[31],k; 8  9 int main()10 {11     scanf("%d",&t);12     num[0]=1;13     for (int i=1;i<=19;i++)14      num[i]=num[i-1]*3;  //预处理15     while (t--)  //t组数据16     {17         scanf("%d%d",&n,&m);18         if (!m)   //特判，没有移动19         {20             for (int i=1;i