这是蒟蒻的第一篇题解。

这道题其实只需要用递归就行了。但是由于数据大，要开高精度。

我们假设三个柱子分别为 A ， B ， C ，可以发现，移动 N 个圆盘的方法就是：

• 先借助 C 柱把 N-1 给圆盘移到B柱；
• 把 A 柱的一个圆盘移到 C 柱；
• 借助 A 柱把 B 柱的 N-1 给圆盘移到 C 柱。

其中，如何移动“ N-1 ”个圆盘，请再阅读一遍。如果只有一个圆盘，特判输出1就行了。

懒得放代码 为了防止抄题解，就不放代码了（？）。

其实，这道题还有一个更简单的方法（一个公式）：

证明方法很简单，自行 bdfs （百度优先搜索）。