Problem 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

Recommend
lcy

大意——符号三角形的第1行有n个由“+”和“-”组成的符号，以后每行符号比上行少1个，2个同号下面是“+”，2个异号下面是“-”。问：计算有多少个不同的符号三角形，使其所含“+”和“-”的个数相同。输出n及个数。

思路——因为n最大为24，所以写一个暴力程序打表即可。而且要使得+和-相等，所以满足n*(n+1)/2等于奇数的n输出为0。然后把+看做0，-看做1，这样就可以通过异或运算求出。

复杂度分析——时间复杂度:O(1),空间复杂度:O(n)

附上AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const double pi = acos(-1.0);
const double e = exp(1.0);
const int num[25] = {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 main()
{ios::sync_with_stdio(false);int n;while (scanf("%d", &n)==1 && n!=0){printf("%d %d\n", n, num[n]);}return 0;
}