← 返回题目列表

AtCoder · abc367_c

F. 枚举序列

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

打印所有长度的整数序列 N 满足以下条件,按字典升序排列。

  • 的 i-第一个元素介于 1 和 R_i,包括在内。
  • 所有元素的总和是以下的倍数 K.
序列的字典顺序是什么? 一个序列 A = (A_1, \ldots, A_{|A|}) is 按字典顺序较小 比 B = (B_1, \ldots, B_{|B|}) 如果下面的 1. 或 2. 成立:
  1. |A|<|B| 和 (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
  2. 存在一个整数 1\leq i\leq \min\{|A|,|B|\} 使得以下两项均成立:
    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
    • A_i < B_i

约束

  • 所有输入值均为整数。
  • 1 \le N \le 8
  • 2 \le K \le 10
  • 1 \le R_i \le 5

输入

输入由标准输入按以下格式给出:

N K
R_1 R_2 \dots R_N

输出

按以下格式打印答案,其中 X 是要打印的序列数, i- 其中第一个是 A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

示例输入 1

3 2
2 1 3

示例输出 1

1 1 2
2 1 1
2 1 3

要打印三个序列,分别是 (1,1,2),(2,1,1),(2,1,3) 按字典顺序排列。


示例输入 2

1 2
1

示例输出 2


可能没有要打印的序列。
在这种情况下,输出可以为空。


示例输入 3

5 5
2 3 2 3 2

示例输出 3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1