【描述】
“漢諾塔”，是一個(gè)眾所周知的古老游戲。現(xiàn)在我們把問題稍微改變一下：如果一共有4根柱子，而不是3根，那么至少需要移動(dòng)盤子多少次，才能把所有的盤子從第1根柱子移動(dòng)到第4根柱子上呢？
為了編程方便，您只需要輸出這個(gè)結(jié)果mod 10000的值。
【輸入】
一個(gè)正整數(shù)n。（0<n<=50000）
【輸出】
一個(gè)正整數(shù)，表示把n個(gè)盤子從第1根柱子移動(dòng)到第4根柱子需要的最少移動(dòng)次數(shù)mod 10000的值。
【樣例輸入】
15
【樣例輸出】
129
【分析】
弄出前幾個(gè)數(shù)，發(fā)現(xiàn)規(guī)律。
f[1]=1，之后分別是加2個(gè)2，加3個(gè)4，加4個(gè)8，加5個(gè)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: