Expression Counting | 2009 Shanghai Invitation Contest Host by DHU

题目描述

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.

输出解释

For each test case, output the number of distinct expressions involving n different operands. Since the answer is very large, you only need to output the answer modulo 1,000,000,007.

输入样例

输出样例

提示

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.

来自杭电HDUOJ的附加信息

Recommend

zhuweicong

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2009 Shanghai Invitation Contest Host by DHU

源链接： HDU-3204

最后修改于 2020-10-25 23:01:09 UTC 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	32768/32768K(Java/Others)