Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Description

+ + – + – + +
+ – – – – +
– + + + –
– + + –
– + –
– –
+

Input

Output

n和符号三角形的个数.

Sample Input

15

16

19

20

0

Sample Output

15 1896

16 5160

19 32757

20 59984

Source

ECJTU 2008 Autumn Contest

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;
for (int i = 0; i <= 1; 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;
}
*/