【描述】
“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？
为了编程方便，您只需要输出这个结果mod 10000的值。
【输入】
一个正整数n。（0<n<=50000）
【输出】
一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。
【样例输入】
15
【样例输出】
129
【分析】
弄出前几个数，发现规律。
f[1]=1，之后分别是加2个2，加3个4，加4个8，加5个16……
1: #include <stdio.h>
2: #define maxn 50010
3:
4: int a,b;
5: int k=1,t;
6: long long j=1;
7: int n;
8:
9: int main()
10: {
11: freopen("hnoi.in","r",stdin);
12: freopen("hnoi.out","w",stdout);
13:
14: scanf("%d",&n);
15: b=1;
16: for (int i=2;i<=n;++i)
17: {
18: a=b;
19: if (!t)
20: {
21: t=++k;
22: j*=2;
23: j%=10000;
24: }
25: b=(a+j)%10000;
26: --t;
27: }
28: printf("%d\n",b);
29: return 0;
30: }
31: