CF1804H Code Lock

Lara 有一个保险箱，保险箱的锁是一个圆形密码锁，由一个可旋转的指针、指针周围的静态圆周、一个输入屏幕和一个输入按钮组成。 锁的圆周被均分为 $k$ 个区域，这些区域按顺时针顺序从 $1$ 到 $k$ 编号。指针总是指向某一个区域。每个区域都用前 $k$ 个英文字母中的一个字母标记，且没有两个区域标记相同的字母。 由于锁的限制，保险箱的密码是一个长度为 $n$ 的字符串，只包含前 $k$ 个英文字母。Lara 通过旋转锁的指针并按下输入按钮来输入密码。最初，锁的指针指向第 $1$ 区域，输入屏幕为空。在一秒内，她可以执行以下操作之一： - 顺时针将指针旋转一个区域。如果指针原本指向第 $x$ 区域且 $x < k$，则现在指向第 $x+1$ 区域。如果原本指向第 $k$ 区域，则现在指向第 $1$ 区域。 - 逆时针将指针旋转一个区域。如果指针原本指向第 $x$ 区域且 $x > 1$，则现在指向第 $x-1$ 区域。如果原本指向第 $1$ 区域，则现在指向第 $k$ 区域。 - 按下输入按钮。指针当前指向的区域上的字母会被添加到输入屏幕的内容中。 一旦输入屏幕上的内容与密码完全一致，保险箱就会打开。Lara 总是以最短时间输入密码。Lara 最近发现这个锁可以重新编程。她可以将前 $k$ 个英文字母以任意顺序分配给各个区域。现在她想要重新排列这些字母，使得输入密码所需的总时间最少。请计算最少所需的秒数，以及有多少种分配字母的方式可以达到这个最小秒数。 如果存在至少一个区域 $i$ 被分配了不同的字母，则认为两种分配方式不同。

输入的第一行包含两个整数 $k$ 和 $n$（$2 \leq k \leq 16$，$2 \leq n \leq 100\,000$），分别表示锁的区域数和密码的长度。 输入的第二行包含一个长度为 $n$ 的字符串，只包含前 $k$ 个小写英文字母。该字符串即为密码。

第一行输出 Lara 输入密码并打开保险箱所需的最小秒数（在最优分配字母的情况下）。 第二行输出有多少种分配字母的方式可以达到这个最小秒数。

下图展示了第一个样例的最优分配初始状态。  下图展示了第二个样例的最优分配初始状态。  下图展示了第三个样例的最优分配初始状态。  由 ChatGPT 4.1 翻译