← 返回题目列表

Codeforces · 1804/H

H. 密码锁

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

劳拉有一个保险箱,用圆形密码锁锁住,密码锁由旋转箭头、箭头周围的静态圆周、输入屏幕和输入按钮组成。

锁的圆周被分成 $$$k$$$ 等份,按顺时针顺序从 $$$1$$$ 到 $$$k$$$ 编号。箭头始终指向其中一个部分。每个部分都标有英文字母表中前 $$$k$$$ 字母之一。没有两个部分标有相同的字母。

由于锁的限制,保险箱的密码是一个长度为 $$$n$$$ 的字符串,仅由英文字母表的前 $$$k$$$ 个字母组成。劳拉通过旋转锁的箭头并按下输入按钮来输入密码。最初,锁的箭头指向 $$$1$$$ 部分,并且输入屏幕为空。一秒钟内她可以执行以下操作之一。

- 将箭头顺时针旋转一节。如果箭头指向 $$$x < k$$$ 部分,它现在将指向 $$$x + 1$$$ 部分。如果箭头指向 $$$k$$$ 部分,它现在将指向 $$$1$$$ 部分。
- 将箭头逆时针旋转一段。如果箭头指向 $$$x > 1$$$ 部分,它现在将指向 $$$x - 1$$$ 部分。如果箭头指向 $$$1$$$ 部分,它现在将指向 $$$k$$$ 部分。
- 按输入按钮。箭头所指部分标记的字母将被添加到输入屏幕的内容中。

劳拉最近发现保险箱可以重新编程。她可以取出英文字母表中的前 $$$k$$$ 字母,并按照她喜欢的任何顺序将它们分配给扇区。现在,她想重新排列字母,以尽量减少输入密码所需的秒数。计算该最小秒数以及实现该最小秒数的分配字母的方式数量。

如果存在至少一个扇区 $$$i$$$ 被分配了不同的字母,则两种为扇区分配字母的方法被认为是不同的。

输入

输入的第一行包含两个整数 $$$k$$$ 和 $$$n$$$ ($$$2 \leq k \leq 16$$$, $$$2 \leq n \leq 100\,000$$$)——分别是锁圆周上的扇区数和 Lara 密码的长度。

输入的第二行包含长度为 $$$n$$$ 的字符串,仅由英文字母表的前 $$$k$$$ 小写字母组成。该字符串就是密码。

输出

在第一行打印 Lara 输入密码并打开保险箱所需的最短秒数(如果她以最佳方式将字母分配给扇区)。

在第二行打印最佳分配字母的方法数。

示例

输入 #1

3 10
abcabcabca

输出 #1

19
2

输入 #2

4 20
bcbcbcbcadadadadcbda

输出 #2

40
2

输入 #3

4 6
adcbda

输出 #3

12
4

注意

第一个示例的最优布置的初始状态如下图所示。

第二个例子的最优布置的初始状态如下图所示。

第三个例子的最优布置的初始状态如下图所示。