bzoj#P1600. [Usaco2008 Oct]建造栅栏

[Usaco2008 Oct]建造栅栏

题目描述

勤奋的 Farmer John 想要建造一个四面的栅栏来关住牛们。他有一块长为 nn 的木板,他想把这块木板切成四块。这四块小木板可以是任何一个正整数长度只要 Farmer John 能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。

注意:

  • 只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况。
  • 栅栏的面积要大于 00
  • 整块木板都要用完。

输入格式

一行一个整数 nn

输出格式

一个整数表示合理的方案总数。

样例输入

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)$。

下面四种 (1,1,1,3); (1,1,3,1); (1,3,1,1) ; (3,1,1,1)(1,1,1,3);\ (1,1,3,1);\ (1,3,1,1)\ ;\ (3,1,1,1) 不能够组成一个四边形。

数据规模与约定

对于 100%100\% 的数据,保证 4n2500\ 4 \leq n \leq 2500,保证答案在 long long 范围内。

题目来源

资格赛