〖摘要〗
　　本文主要利用组合数学的思想解计数问题，然后递推求特定序列。

〖前言〗
　　本题改编自URAL题库的1148（http://acm.timus.ru/problem?id=1148），并且由我加以了简化。事实上，我是不会做英文原题的（-_-），即便是本题，任务二解决得也很不好，所以这里不详细写。希望有好算法的同学与我联系，让我的论文能抛砖引玉。大家共同探讨，然后共同进步。E-mail Address：Lymail@263.net。

〖题目描述〗
　　用无限块积木搭h层的塔a[1..h]，相邻层的积木数差为1，即 。塔的第一层必须有m块积木（）关于塔的比较的定义这里不再累赘地叙述了。
　　任务1：求不同的塔的种类数。
　　任务2：把塔排序，根据塔的id，求塔的形状。

〖正文〗
　　由于题目对塔的定义明显具有这样的性质：如果a[1..h]是一座合法的塔，那么a[1..h-1]必定也是合法的塔。换一个角度，高度为h，底层有m块积木的塔（以下记为"塔（h,m）"），去掉第一层以后，必定是以下两种塔之一：塔（h-1，m-1）或塔（h-1，m+1）。我们就可以把求塔（h，m）的种类数，转变为分别求塔（h-1，m-1）与塔（h-1，m+1）的种类数的子问题。同时我们可以知道，不可能存在塔（?，0）。经过这样的推理，任务一的一个最简单的递推关系式已经诞生了：

　　算法1.1，计算塔（h，m）的种类数

　　记f（h，m）为塔（h，m）的种类数。
　　　f（h，m）= f（h-1，m+1）+ f（h-1，m-1）
　　　f（x，0）= 0，x > 0
　　　f（1，y）= 1，y > 0

　　现在让我们来分析一下这个算法的复杂度。我们要计算f（h，m），首先要知道f（h-1，m+1）与f（h-1，m-1），要算这两个又必须知道f（h-2，m-2），f（h-2，m-1）与f（h-2，m-3）……最后，在h <= m的情况下我们大约一共要算（h + 1） h / 2个f函数，每次计算的复杂度为O（1），所以总的时间复杂度接近O（h^2）。问题是按照这样的计算，f（h，m）很容易在h很小的情况下就突破普通编程语言的数据范围，所以本题必须使用高精度。这样高精度的加法运算至少要在计算中再添加一个O（n）（n为常数）的内嵌过程，总复杂度达到O（h^2n）。看一下题目中h的范围，失败的阴影在我们心头掠过……

　　怎么优化呢？要知道，我们还在做任务一啊！仔细研究发现，我们对时间的浪费主要在于f函数的计算。我们使用了复杂度为O（h^2）的算法，而面对题目要求的h，这明显是不可能实现的。事实上经验告诉我们，像这种看起来"经典"无比的递推计数题往往存在组合数的解法，这种解法往往是O（n）乃至更小的。本题能否利用组合计数呢？

　　明确了关键，再经过一段思考，我发现本题可以转换成如下的模型：
　　从层i到层i+1，积木数的变化不是加一就是减一。一座h层的塔，积木数就变化了h-1次。如果把积木数的加一记为0，减一记为1，由于塔的第一层a1已经确定，任何一种塔事实上都与一个长度为h-1的二进制字符串一一对应；例如塔（4，3，2，3），就代表了二进制串110，塔（4，3，2，1）代表111……至于出现塔的某层积木数为0的非法情况，则可以认为是二进制串b[1..h-1]中存在某位i，串b[1..h-1]中1的数量比0的数量多m，即 |1| - |0| = m。一座合法的塔就是不存在这种现象的二进制串。

　　这样的模型有甚么用呢？如果一个长h-1的二进制串中间的1的数量是已知的，很容易利用组合分析获得符合以上条件的二进制串的数量。具体的计算方法如下：

　　算法2.1：计算长度h-1，含x个1，且到任何位为止，| 1 | - | 0 | < m的二进制串的个数

　　记该函数为g（x，h-1，m），则有
　　g(x,h-1,m)=-
　　特别的
　　若x >= (h - 1 + m) /2，有
　　g(x,h-1,m)=0
　　若x < m，有
　　g(x,h-1,m)=
　　算法的证明如下。

　　如果不存在限制条件，符合要求的二进制串明显有个。若x < m，即使加上限制条件符合要求的串也不会有丝毫的减少，这是显而易见的。
　　加上限制条件以后，如果存在合法的串，那么1的个数x最多也不能比0的个数h-1-x多m，即x - m < h - 1 - x，整理得x < (h - 1 + m) / 2。

　　假使 x >= m，至少存在一个不符合条件的二进制串；且x < (h - 1 + m) / 2，至少存在一个合法的串。怎么计算不合法的串的总数呢？一般采用变换法，也就是某些类似模型里的非降路径翻转法。

　　设有一个不合法串b[1..h-1]，必定存在一个最小的正整数y，y < (h - 1 + m) / 2，在b[1..2y - m]里存在y个1，y-m个0。那么b [2y - m + 1..h-1]里就有x-y个1，h - 1 - x - y + m个0。如果把b [2y - m + 1..h-1]的串全部变换，0变1，1变0，就会将原串变成一个由 h-1-x+m个1，x-m个0组成的新串。容易证明，如果2个不合法的原串不同，新串也肯定不同。

　　设有一个串c[1..h-1]，有h-1-x+m个1，x-m个0。由于x < (h - 1 + m) / 2 ，有
| 1 | - | 0 | = h-1-x+m-x+m = h-1 -2x +2m > h-1 - (h-1+m)+2m = m，所以一定会出现1的个数比0的个数多m的情况。取一个最小的正整数y，y < (h - 1 + m) / 2，在c[1..2y - m]里存在y个1，y-m个0，对c[2y-m+1..h-1]做对称变换，这样原串就变为一个新串b[1..h-1]，有x个1，h-1-x个0，且b[1..h-1]是不合法的。同样也容易证明，如果2个c串不同，b串也肯定不同。现在，根据上面两段推理，我们可以庄严地宣布：
　　每一个不合法的子串b[1..h-1]，总与一个由h-1-x+m个1，x-m个0组成的串c[1..h-1]对应，从而不合法串b[1..h-1]的数量，等于对应的c[1..h-1]的数量，即 。
　　由此就推出了上面那个公式，同时任务一的第二种算法也成型了。

　　算法2.2：计算f（h，m）的数量
　　f（h，m）= sum [g（x，h-1，m），x = 0..h-1 ]
　　具体实现上，分别用算法2.1求每个g（x，h-1，m），然后加起来。
　　现在重新计算一下复杂度。Sum是O（h）的，算法2.1由2个O（h）的组合数运算与一个O（n）的高精度加法并排构成，内部有一个O（n）的高精度乘法过程。总的时间复杂度还是O（h^2n）！但是，我们必须看到，组合数的运算这个O（h）的O是很小的，所以目前的算法对比算法1.1来，实际上已经好了很多。

　　可是，我们的努力难道只有这么一点效果吗？当然不是的。事实上上面算法2.2的实现方法存在着极大的浪费，这个浪费主要表现在2个方面：对组合数的计算的浪费与具体的组合数计算过程中的浪费上。
　　首先，设m = 1。所以有
　　f（h，1）= g（0，h-1，1）+ g（1，h-1，1）+ L + g（h-1，h-1，1）
　　　　　　　= C（1，h-1） +
　　　　　　　　C（2，h-1）- C（1，h-1）+
　　　　　　　　C（3，h-1）- C（2，h-1）+
　　　　　　　　L +
　　　　　　　　C（h-1，h-1）- C（h-2，h-1）

　　可以看到，在计算的过程中出现了大量重复计算的组合数，以及一大堆事实上根本无需计算的组合数（需要注意的是，不能光凭上面这个并不严密的等式断定f（h，1）= C（h-1，h-1），因为在计算的过程中许多函数g可能在算法2.1里被直接赋成0）。事实上，我们可以建一个O（h）的byte型数组times[0..h-1]来纪录每个组合数最后的系数。在开始计算f（h，m）前先通过一个O（h）的循环确定times[0..h-1]，然后在计算过程里根据每个组合数计算的最终次数决定不计算或者仅进行简单的计算。
　　其次，由于组合数本身的定义，有等式C（m，n）=C（m，n-1） (m - n + 1) / n，所以事实上两个O（n）的高精度计算过程就足以计算从C（m，n-1）出C（m，n）了。i.e.算出全部组合数的复杂度也只有O（h，n）。
　　那么我们就得到了以下算法

　　算法2.3：算法2.2的优化

　　0， 简单赋值C（-1，h-1）（这里要当成是1，不能赋成0）；简单清空times；
　　1， 按顺序计算每个组合数C（x，h-1），同时修改times[x]与times[x-m]：
　　　　1.1， 若x >= (h-1+m) / 2，跳回到1计算下个x。
　　　　1.2， inc（times[x]）；
　　　　1.3， 若x >= m，dec（times[x-m]）；
　　2， 综合计算出结果。
　　以上算法的时间复杂度为O（h n），空间复杂度为O（h + n）（n均为小的常数）用于解决任务一应该是足够的了。
（松了一口气……）

　　开始解决任务二。与前面相似地，一座塔（h,m）去掉第一层以后必定是以下两种塔之一：塔（h-1，m-1）或塔（h-1，m+1）。且总有：塔（h-1，m-1）<塔（h-1，m+1）。这样若告诉我们的塔序号C <= f（h-1，m-1），我们就知道a[2] = m - 1，否则a[2] = m+1。这种递推的复杂度为O（h），内部是复杂度为O（h n）的算法2.3，总复杂度O（h^2 n）。看起来复杂度很大啊！……没办法，我没想出更好的，否则1148就可以解决了。暂时只好先用这个算法吧，应付本题是够了的。^_^

　　算法3.1：任务二

　　1， 获得塔序号C；
　　2， 比较C与f（h-1，m-1）；
　　　　2.1，若C > f（h-1，m-1），从C里减去f（h-1，m-1），a[2] = m+1，转到　　　　　2.3；
　　　　2.2，否则 a[2] = m-1；
　　　　2.3，跳回2，确定a[3]，如果推完了就打印；

　　更好的算法探求中……