#P3366. [Usaco2004 Feb]Breeding 奶牛饲育
[Usaco2004 Feb]Breeding 奶牛饲育
[USACO 2004 Feb] Breeding 奶牛饲育
题目描述
约翰从一头母牛开始扩增牛群。他可以调节饲料用量,使同一代的每头母牛都产下相同数量的牛犊。每头母牛在一代中至少产下 头牛犊,产仔数没有上限。母牛产仔后就会被卖掉,因此农场里只保留最新一代的牛。
例如,开始时让唯一的母牛产下 头牛犊,再让这 头牛各产下 头牛犊,就能得到 头牛。两种方法只要有一代每头牛的产仔数不同,或者经历的代数不同,就视为不同的方法。
求得到恰好 头牛的方法数。若 ,可以保留最初的一头牛,不进行繁殖。
输入格式
从标准输入读入一行一个整数 。
输出格式
向标准输出输出一行一个整数,表示方式总数。
12
8
样例解释
一种方法是 ,即前两代每头产 头,第三代每头产 头。其他七种方法是 、、、、、 和 。
数据范围与约定
,方法总数不超过 。