| Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 。 n=7时的1个符号三角形如下:
+ + – + – + +
+ – – – – +
– + + + –
– + + –
– + –
– –
+
Input
每行1个正整数n <=24,n=0退出.
Output
n和符号三角形的个数.
Sample Input
15
16
19
20
0
Sample Output
15 1896
16 5160
19 32757
20 59984
Source
ECJTU 2008 Autumn Contest
思路：枚举第一行，后面便随之确定。符号确定规则与异或运算法则相同，所以用0 1表示+ -（顺序无所谓）能简化运算，当0和1个数相同时即为有效状态。本地DFS打表再提交。
AC代码，注释部分为打表代码：
#include <cstdio>
int main()
{
const int ans[] = {0, 0, 0, 4, 6, 0, 0, 12, 40, 0, 0, 171, 410, 0, 0, 1896, 5160, 0, 0, 32757, 59984, 0, 0, 431095, 822229};
int n;
while (scanf("%d", &n) && n)
printf("%d %d\n", n, ans[n]);
return 0;
}
/*
#include <cstdio>
using namespace std;
bool map[30][30] = {0};
int ans[30] = {0};
void dfs(int depth, int sum)
{
if (depth > 24)
return;
int add;
for (int i = 0; i <= 1; i++)
{
add = map[1][depth] = i;
for (int j = 2; j <= depth; j++)
{
map[j][depth - j + 1] = map[j - 1][depth - j + 1] ^ map[j - 1][depth - j + 2];
add += map[j][depth - j + 1];
}
if ((sum + add) * 2 == depth * (depth + 1) / 2)
ans[depth]++;
dfs(depth + 1, sum + add);
}
}
void solve()
{
dfs(1, 0);
for (int i = 1; i <= 24; i++)
printf("%d, ", ans[i]);
}
int main()
{
solve();
return 0;
}
*/