NOI2.5-2990符号三角形
4276+
题目大意：一个三角形有加号减号组成，且两个同号下是加号，异号下是减号，如果最长边是n，请问共有多少种不同的三角形？
题目描述
符号三角形的第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同。
n=7时的1个符号三角形如下:
+ + - + - + + + - - - - + - + + + - - + + - - + - - - +
输入
每行1个正整数n<=24,n=0退出.
输出
n和符号三角形的个数.
样例输入
15
16
19
20
0
样例输出
15 1896
16 5160
19 32757
20 59984
提示
实际数据：n<=22
解题思路
按照题目的意思，逐行枚举，先枚举第一行的加减号，枚举时，可以把加号看成0，减号看成1，相同下面是加号，不同下面是减号，恰好位运算的异或运算符的运算规则。第一行的范围是0到(1<<n)-1，下一行可以由上一行通过异或得到：下一行=上一行^上一行*2，然后去头去尾就行。这样，一边推导，一边统计加减号个数（减号个数即1的个数），如果有一个符号超过一半，不用继续搜索（可行性剪枝）。最后如果加减号相同个数，方案数加1。可以预处理2的k次方以及2的n次方以内所有数的二进制中1的个数，时间复杂度O(n*2n)。
这种算法，在暴力算法中还算是高效的，但是剪枝还不够多，因为他枚举的范围还是2n，后面剪枝也只能剪很少部分的枝。能不能剪掉枚举范围的枝呢？可以的，倒过来枚举搜索：从小行到大行枚举，只需要确定每一行的第一个字符，那么同一行后面的都可以逐个推出来。同样，在搜索过程中，遇到加号或者减号超过一半，就退出搜索，这样后面有些行首就不需要枚举了，枚举的范围就少了。当然，时间复杂度还是O(n*2n)，但剪枝剪更多了。
实测以上两种算法，分开枚举每一行首字符，速度快一倍。但如果要更快，可以尝试记忆化搜索，如预处理前几行的加减号个数等。如果用位运算，预处理出n=20的所有符号三角形的加减号个数，再在此基础上算n=23、24的符号三角形数目，速度会快很多。
程序实现
