bzoj#P1600. [Usaco2008 Oct]建造栅栏
[Usaco2008 Oct]建造栅栏
题目描述
勤奋的 Farmer John 想要建造一个四面的栅栏来关住牛们。他有一块长为 的木板,他想把这块木板切成四块。这四块小木板可以是任何一个正整数长度只要 Farmer John 能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。
注意:
- 只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况。
- 栅栏的面积要大于
- 整块木板都要用完。
输入格式
一行一个整数 。
输出格式
一个整数表示合理的方案总数。
样例输入
6
样例输出
6
样例说明
Farmer John 能够切出所有的情况为:
$(1,1,1,3)\ ;\ (1,1,2,2);\ (1,1,3,1);\ (1,2,1,2)\ ;\ (1,2,2,1);$
$(1,3,1,1)\ ;\ (2,1,1,2);\ (2,1,2,1);\ (2,2,1,1)\ ;\ (3,1,1,1)$。
下面四种 不能够组成一个四边形。
数据规模与约定
对于 的数据,保证,保证答案在 long long
范围内。
题目来源
资格赛