吐槽题目 叫什么很O_O的汉诺塔我还@。@呢。
本来是想过一段时间在来写题解的，不过有人找我要。
本来排名是第8的。然后搞了半天，弄到了第五。不过代码最短~
截止目前就9个ID过，小小的成就感~
PS用G++内存小。。。
| Rank | Author | Exe. Time | Exe. Memory | Code Len. | Language | Date |
| 1 | 4bytes | 0MS | 204K | 1961B | C++ | 2011-07-30 22:15:19 |
| 2 | sunhaowen | 0MS | 212K | 895B | G++ | 2009-05-25 14:17:40 |
| 3 | ecjtuzhousc存档 | 0MS | 232K | 4614B | G++ | 2011-10-12 11:50:22 |
| 4 | guoxiang | 0MS | 244K | 893B | C++ | 2009-05-31 13:18:57 |
| 5 | hr_whisper | 0MS | 248K | 720B | G++ | 2013-08-13 10:41:31 |
| 6 | acm29026 | 0MS | 260K | 4614B | C++ | 2009-05-25 10:24:36 |
| 7 | hdjt2009 | 0MS | 260K | 4614B | C++ | 2009-05-25 10:39:56 |
| 8 | topsky | 0MS | 276K | 923B | C++ | 2009-05-25 15:08:17 |
| 9 | ACOrz | 0MS | 372K | 1019B | G++ | 2009-12-30 20:39:05 |
做这题一定要耐心。
先来简单的例子，如果m=1，也就是n种，每种1个。
那就是简单的汉诺塔。但题目要求路径为A->B ,B->C,C->A
可以这样：设n种时答案为a[n]，（因为形成一个环，也可以理解为间隔一个移动的步数。）
1、n-1个盘子A移动到C ，a[n-1]
2、第n个从A->B ，1次。
3、n-2个盘子C->B ,a[n-2]
4、第n-1个盘子C->A ，1
5、n-2个盘子C->A ，a[n-2]
6、第n个从B->C ，1次。
7、n-1个盘子A移动到C ，a[n-1]
总的为a[n-1] + 1 + a[n-2] + 1 + a[n-2] + 1 + a[n-1]=2 * a[n-1]+ 2* a[n-2]+3
题目的要求是最后排列所有相等大小盘按原来从上到下次序，所以若m不为1，答案不是简单的m*a[n]（我一开始就是直接。。。。。要不要这样T T）
讨论m>2的情况，等于2呢？别着急等下说。
设答案a[n],
b[n]为m>2间隔移动的步数,移动后倒数第二类是反的（如A->C,C->B），
c[n]也为间隔移动，但是是最后几个顺序颠倒的移动（在n类是反的和n-1类是反的的情况下）（注意和b[n]区别，一个是移动前一个是后）。
d[n]为m>2相邻移动的步数，移动后倒数第一类是反的（如A->B,B->C,C->A）
例子以n=3,m=3的例子，1~3大小相同，为第一类。4~6同，7~9同写在前面的在上面
1、n-1类盘子A移动到C ，b[n-1]（是类哦，不是个哦）
A:789
B:
C:321456
2、第n类一个个到B ，m
A:
B:987
C:321456
3、n-1类移动到A ， d[n-1]
A: 321654
B:987
C:
4、第n类一个个到C, m
A: 321654
B:
C: 789
5、从A到C，但最后几个是反的，c[n-1]
A:
B:
C: 123456789
得到a[n]= b[n-1]+ d[n-1]+ c[n-1]+2*m;
一个个接着剖析。
要实现b[n]怎么弄？以从A->C为例
1、n-1类 A->C , b[n-1]
2、第n类A->B , m
3、n-1类 C->A , d[n-1]
4、第n类B->C , m
5、n-1类 A->C , b[n-1]
所以b[n]= 2*b[n-1]+2*m+d[n-1]
d[n]呢以从A->B为例
1、n-1类 A->C , b[n-1]
2、第n类A->B , m
3、n-1类 C->B, b[n-1]
所以d[n]= 2*b[n-1]+ m;
但你有木有发现，这样移动到相邻最底下顺序是反的！而用b的移动方法，第n-1类是反的。所以上面才会有c[n]的出现。
c[n]的目标很明确，在n是反的和n-1是反的的情况下，移动间隔。从A->C为例
1、n-1类从A->C ，n-2变反了，n-1反 。b[n-1]
2、第n类从A->B，（但是坑爹了，他是正顺，移动到C就会倒序！），m
3、n-1类从C->A n-1正 ，d[n-1]
4、第n类从B->C， 反 ，m
5、n-1类从A->B n-1反 ，d[n-1]
6、第n类从C->A， 正 ，m
7、n-1类从B->C n-1正 ，d[n-1]
8、第n类从A->B， 反 ，m
9、n-1类从C->A n-1反 ，d[n-1]
10、第n类从B->C， 正 ，m
11 n-1类从A->C ，c[n-1] (现在n-1和n-2都是反的，往下递归)
c[n]= b[n-1]+ m+4*(d[n-1]+m)+c[n-1];
感觉坑爹?嗯没错！但还有更坑的。
m=2怎么办？
这是个特殊的，它的c[n]不符合上述规律，为什么？
假设n=5,m=2,同样编号，2号为一类
经过和前面一样的步奏（见前面n=3,m=3的例子，n-1类移动回A后第n-1和第n-2类反了）
此时同样以A->C为例子。别忘了C[n]的目的。（n-1、n类都是反的）
你把1~6号移动到C的话，把8号移动到B而7号可以不动！！！
这样等下可以直接8号到C而不用坑爹的像上面一样移动4次！
过程如下
初始
A 12346587
B
C 9 10（对以后无影响，下面不写了，同样，为了方便n=4，下面就直接c[n]而不用c[n-1]了）
1、1~6移动到C ，b[n-1]
A 87
B
C 124365
2、8号到B ，1
A 7
B 8
C 124365
3、124365移动到A ，d[n-1]
A 1243567
B 8
C
4、8号到C ，1
A 1243567
B
C 8
5、124356到C ，b[n-1]
A 7
B
C 1234568
6、7到B ， 1
A
B 7
C 1234568
7、123456到A ，d[n-1]
A 123465
B 7
C 8
8、7号到C （与开始不同，开始是后面两类倒着的，所以得继续推） ，1
A 123465
B
C 78
9、1~4到C ， b[n-2]
A 65
B
C 213478
10、6到B ， 1
A 5
B 6
C 213478
11、 2134到A ，d[n-2]
A 21435
B 6
C 78
12、6到C ，1
A 21435
B
C 678
13、2143到C ，b[n-2]
A 5
B
C 1243678
14、5到B ，1
A
B 5
C 1243678
15、1243到A ， d[n-2]
A 1234
B 5
C 678
16、5到C （有木有发现现在1234顺序是正的！！！）， 1
A 1234
B
C 5678
17、1234到C （直接调用答案） a[n-2]
综上：
m=2时，
C[n]=b[n-1] +1
+ d[n-1] +1+b[n-1]+1+d[n-1]+1
+b[n-2]+1+
d[n-2]+ 1+ b[n-2]+1+d[n-2]+1+a[n-2]
=2* b[n-1]+ 4+ 2* d[n-1]+2* b[n-2] +4+2* d[n-2]+a[n-2]
m=1就是一开始分析的了。
坑爹吧？
OKOK上代码~
#include<cstdio>
const int mod = 20090308;
const int MAXN=1002;
long long a[MAXN],b[MAXN],c[MAXN],d[MAXN],m;
int n;
int main()
{
a[0]=b[0]=c[0]=d[0]=0;
while(scanf("%d%I64d",&n,&m)!=EOF)
{
if(m==1)
{
a[1]=2;
for(int i=2;i<=n;i++)
a[i] =( 2 * a[i-1]+ 2* a[i-2]+3 ) % mod;
}
else
{
a[1]=b[1]=c[1]=2*m;
d[1]=m;
for(int i=2;i<=n;i++)
{
d[i]= ( 2*b[i-1]+ m ) % mod;
b[i]= ( 2*b[i-1]+2*m+d[i-1] ) % mod;
if(m==2)
c[i]=( 2* b[i-1]+ 4+ 2* d[i-1]+2* b[i-2] + 4+2* d[i-2] +a[i-2] ) %mod;
else
c[i]=( b[i-1]+ m+4*(d[i-1]+m)+c[i-1] ) % mod;
a[i]= ( b[i-1]+ d[i-1]+ c[i-1]+2*m ) % mod;
}
}
printf("%d\n",a[n]);
}
return 0;
}