LG#P2089. 烤鸡

烤鸡

P2089 烤鸡

题目描述

\hspace{15pt}猪猪 Hanke 特别喜欢吃烤鸡。他吃鸡的方式很特别:他有 1010 种配料,每种配料可以放 11 到 33 克,一只烤鸡的美味程度定义为所有配料的质量之和。

\hspace{15pt}现在给定一个美味程度 nn,请你输出这 1010 种配料的所有搭配方案。

∙ \hspace{15pt}\bullet\,字典序:从两个序列的第一个元素开始逐个比较,直到找到第一个不同的位置,通过比较这个位置元素的大小得出两个序列的大小,称为字典序比较。

输入格式

\hspace{15pt}输入一行一个整数 n(1≦n≦104)n \left(1 \leqq n \leqq 10^4\right) 代表美味程度。

输出格式

\hspace{15pt}第一行输出一个整数,代表满足要求的方案总数。

\hspace{15pt}此后每行输出 1010 个整数,依次代表这 1010 种配料的质量,相邻两个整数之间用一个空格隔开。所有方案按字典序排列。

\hspace{15pt}如果不存在满足要求的方案,则只输出一个 00,不需要输出其他内容。

测试样例

11
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1

样例 1 解释

\hspace{15pt}每种配料至少放 11 克,1010 种配料的下界之和为 1010。要凑出 1111,只能是其中恰好一种配料放 22 克、其余九种各放 11 克,而放 22 克的那一种配料有 1010 种选择,因此方案总数为 1010。

\hspace{15pt}这 1010 种方案依次对应「放 22 克」的位置从最后一种到第一种,恰好按字典序排列。

31
0

样例 2 解释

\hspace{15pt}每种配料至多放 33 克,1010 种配料的上界之和为 3030,因此美味程度不可能达到 3131,方案总数为 00。

提示

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1041 \leqq n \leqq 10^4。

\hspace{15pt}每种配料的质量只能是 11、22 或 33,因此只有当 10≦n≦3010 \leqq n \leqq 30 时方案总数才不为 00,且方案总数不超过 310=5.9049×1043^{10} = 5.9049 \times 10^4。