汉诺塔问题
| 试题描述 |
|
现在有围成一圈的三根柱子，初始时，A柱从底向上套有n个大小不等的盘子，B柱和C柱上没有盘子。现在可以做三种操作：1) 将A柱顶端的盘子移到B柱顶端 2) 将B柱顶端的盘子移到C柱顶端 3)将C柱顶端的盘子移到A柱顶端。除此之外，要求在移动的任意过程中，不得出现大盘在上，小盘在下的情况。请求出将n个盘子从A柱移到B柱最少需要多少次移动。 |
| 输入 |
| 仅一个整数N，含义如题所述。 |
| 输出 |
| 仅一个整数M，表示最少的移动次数对10000007取模。 |
| 输入示例 |
| 2 |
| 输出示例 |
| 5 |
| 其他说明 |
| 数据范围：1<=N<=10^6 |
#includeusing namespace std; long long ac[1000001],ab[1000001],n; int main() { cin>>n; ac[1]=2; ab[1]=1; ab[2]=5; ac[2]=7; for(long long i=3;i<=n;i++) { ac[i]=(2*ac[i-1]+ab[i-1]+2)%10000007; ab[i]=(2*ac[i-1]+1)%10000007; } cout<<ab[n]; }