链接：https://ac.nowcoder.com/acm/contest/3004/I
来源：牛客网
 

题目描述

汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

 

汉诺塔以及其衍生问题往往使用递归来求解，也是学习和理解递归很好的老师。

 

其伪代码如下

Function Hanoi(n,a,b,c)
    if n==1 then
        print(a+'->'+c)
    else
        Hanoi(n-1,a,c,b)
        print(a+'->'+c)
        Hanoi(n-1,b,a,c)
    end if
end Function 

 

牛牛很快就理解了代码的意思并且写出了求解汉诺塔的程序，他现在想研究汉诺塔的规律。

请你统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。

 

 

输入描述:

 

仅一行，输入一个正整数n(1≤n≤60)(1 \leq n \leq 60)(1≤n≤60)表示汉诺塔的层数。

输出描述:

 

首先输出6行

A->B:XX
A->C:XX
B->A:XX
B->C:XX
C->A:XX
C->B:XX

分别表示每种移动情况出现的次数

最后输出一行
SUM:XX

表示所有移动情况的总和。

示例1

输入

 

3

输出

 

A->B:1
A->C:3
B->A:1
B->C:1
C->A:0
C->B:1
SUM:7

说明

 

伪代码所示算法的移动序列如下：

A->C

A->B
C->B
A->C
B->A
B->C

A->C

统计：

A->B出现1次

A->C出现3次

B->C出现1次

B->A出现1次

C->B出现1次

总计7次

 

比赛过程中入了杜教BM的坑，始终没有仔细找找规律

规律见代码 

（这算是个dp🐴）强行归为dp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
const int N = 1e5 + 20;

ll a[61][7];

int main()
{
    memset(a, 0, sizeof(a));
    a[1][1] = 0;
    a[1][2] = 1;
    a[1][3] = 0;
    a[1][4] = 0;
    a[1][5] = 0;
    a[1][6] = 0;
    for(int i = 2; i <= 60; ++i)
    {
        a[i][1] = a[i][4] =  2 * a[i - 1][2] - i / 2;
        if(i & 1)
            a[i][2] = a[i - 1][1] + a[i - 1][2] + a[i - 1][3] + 1;
        else
            a[i][2] = a[i - 1][2];
        a[i][3] = a[i][6] = a[i][2] - (i + 1) / 2;
        a[i][5] = a[i][1] - i / 2;
    }
    int n;
    while(~scanf("%d", &n))
    {
        cout<<"A->B:"<<a[n][1]<<'\n';
        cout<<"A->C:"<<a[n][2]<<'\n';
        cout<<"B->A:"<<a[n][3]<<'\n';
        cout<<"B->C:"<<a[n][4]<<'\n';
        cout<<"C->A:"<<a[n][5]<<'\n';
        cout<<"C->B:"<<a[n][6]<<'\n';
        cout<<"SUM:"<<a[n][1] + a[n][2] + a[n][3] + a[n][4] + a[n][5] + a[n][6]<<'\n';
    }
    return 0;
}