← 返回题目列表

Codeforces · 2157/H

H. 注册机 3

中文机器翻译题面 查看原题
特雷·弗雷 - 刷新
⠀

如果长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ 被称为有效,如果它具有以下两个属性:

  • 这是双音$$$^{\dagger}$$$;
  • 其子集中的$$$m$$$ 恰好是周期$$$^{\ddagger}$$$。

令$$$k$$$表示满足上述条件的排列数。您的任务是查找并打印 $$$\min(k, 2000)$$$ 此类排列的示例。

$$$^{\dagger}$$$ 如果存在索引 $$$i$$$ ($$$1 \leq i \leq n$$$) ,则排列 $$$p_1, p_2, \ldots, p_n$$$ 是双调的

  • $$$p_{j-1} \leq p_j$$$ 对于 $$$2 \leq j \leq i$$$;
  • $$$p_j \geq p_{j+1}$$$ 对于 $$$i \leq j \leq n-1$$$。

$$$^{\ddagger}$$$ 子集 $$$C \subseteq \{ 1, 2, \ldots, n \}$$$ 是一个循环,如果它满足以下条件:

  • $$$C$$$ 非空;
  • 如果 $$$x \in C$$$,则 $$$p_x \in C$$$;
  • $$$C$$$ 是最小的,即不存在循环 $$$C'$$$ 使得 $$$C'\子集 C$$$。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

输入由一行组成,其中包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \le m \leq n \le 100$$$) - 排列的长度和目标循环数。

输出

在第一行中,打印一个整数 $$$r$$$:要打印的排列数。请注意,$$$r$$$ 必须是语句中定义的 $$$\min(k, 2000)$$$。

然后,打印 $$$r$$$ 行。每行必须包含长度为 $$$n$$$ 的双音排列,循环为 $$$m$$$。

示例

输入
复制

6 3

输出
复制

9
1 4 5 6 3 2
6 5 4 3 2 1
1 2 4 5 6 3
1 2 5 6 4 3
1 3 4 6 5 2
1 5 6 4 3 2
3 5 6 4 2 1
1 3 6 5 4 2
2 6 5 4 3 1

注意

在示例中,有 $$$9$$$ 有效排列(即,长度为 $$$6$$$ 的双音排列,具有 $$$3$$$ 周期)。例如,$$$[3, 5, 6, 4, 2, 1]$$$ 是双调的(在上面的定义中,$$$i = 3$$$),并且它有 $$$3$$$ 周期:$$$\{1, 3, 6\}$$$,$$$\{2, 5\}$$$,$$$\{4\}$$$。所以你必须打印 $$$r = \min(9, 2000) = 9$$$ 这样的排列。