首页 > ACM题库 > HDU-杭电 > hdu 3204 Expression Counting待解决[解题报告]C++
2014
03-06

hdu 3204 Expression Counting待解决[解题报告]C++

Expression Counting

问题描述 :

YY is a clever boy. One day, he feels very boring and writes some expressions randomly. Later, he discovers that although some expressions were written in different forms, they are essentially the same, such as a+(b-c), (a+b)-c. After several attempts, he becomes interested in this and wants to know the number of distinct expressions involving n different operands.

To make the problem easier, you can assume that only operators +, -, *, / and parentheses are permitted.

输入:

The input consists of multiple test cases.

For each test case, there is one line containing only one integer n. (1<=n<=30)
End of input is indicated by a line containing a zero.

输出:

The input consists of multiple test cases.

For each test case, there is one line containing only one integer n. (1<=n<=30)
End of input is indicated by a line containing a zero.

样例输入:

1
2
3
4
0

样例输出:

1
6
68
1170
Hint
There are 6 distinct expressions involving 2 operands: a+b, a-b, b-a, a*b, a/b, b/a. There are 68 distinct expressions involving 3 operands: a+b+c, a+b-c, a-b+c, a-b-c, b-a+c, b-a-c, c-a-b, a*b*c, a*b/c, a/b*c, a/b/c, b/a*c, b/a/c, c/a/b, a+b*c, b+a*c, c+a*b, a+b/c, a+c/b, b+a/c, b+c/a, c+a/b, c+b/a, a-b*c, b-a*c, c-a*b, a-b/c, a-c/b, b-a/c, b-c/a, c-a/b, c-b/a, b*c-a, a*c-b, a*b-c, b/c-a, c/b-a, a/c-b, c/a-b, a/b-c, b/a-c, a*(b+c), b*(a+c), c*(a+b), a*(b-c), a*(c-b), b*(a-c), b*(c-a), c*(a-b), c*(b-a), a/(b+c), b/(a+c), c/(a+b), a/(b-c), a/(c-b), b/(a-c), b/(c-a), c/(a-b), c/(b-a), (b+c)/a, (a+c)/b, (a+b)/c, (b-c)/a, (c-b)/a, (a-c)/b, (c-a)/b, (a-b)/c, (b-a)/c. When n=4, note that (a-b)/(c-d) and (b-a)/(d-c) are the same, but a/b-c/d and b/a-d/c are not.