Code Lock
Contest: Nebius Welcome Round (Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: bitmasks, dp

Lara has a safe that is locked with a circle-shaped code lock that consists of a rotating arrow, a static circumference around the arrow, an input screen, and an input button.

The circumference of the lock is split into $$$k$$$ equal sections numbered from $$$1$$$ to $$$k$$$ in clockwise order. Arrow always points to one of the sections. Each section is marked with one of the first $$$k$$$ letters of the English alphabet. No two sections are marked with the same letter.

Due to the lock limitations, the safe's password is a string of length $$$n$$$ that consists of first $$$k$$$ letters of the English alphabet only. Lara enters the password by rotating the lock's arrow and pressing the input button. Initially, the lock's arrow points to section $$$1$$$ and the input screen is empty. In one second she can do one of the following actions.

- Rotate the arrow one section clockwise. If the arrow was pointing at section $$$x < k$$$ it will now point at section $$$x + 1$$$. If the arrow was pointing at section $$$k$$$ it will now point at section $$$1$$$.
- Rotate the arrow one section counter-clockwise. If the arrow was pointing at section $$$x > 1$$$ it will now point at section $$$x - 1$$$. If the arrow was pointing at section $$$1$$$ it will now point at section $$$k$$$.
- Press the input button. The letter marked on the section that the arrow points to will be added to the content of the input screen.

Lara has recently found out that the safe can be re-programmed. She can take the first $$$k$$$ letters of the English alphabet and assign them to the sectors in any order she likes. Now she wants to re-arrange the letters in a way that will minimize the number of seconds it takes her to input the password. Compute this minimum number of seconds and the number of ways to assign letters, for which this minimum number of seconds is achieved.

Two ways to assign letters to sectors are considered to be distinct if there exists at least one sector $$$i$$$ that is assigned different letters.

Input format:
The first line of the input contains two integers $$$k$$$ and $$$n$$$ ($$$2 \leq k \leq 16$$$, $$$2 \leq n \leq 100\,000$$$) — the number of sectors on the lock's circumference and the length of Lara's password, respectively.

The second line of the input contains a string of length $$$n$$$ that consists of the first $$$k$$$ lowercase letters of the English alphabet only. This string is the password.

Output format:
On the first line print minimum possible number of seconds it can take Lara to enter the password and open the safe if she assigns letters to sectors optimally.

On the second line print the number of ways to assign letters optimally.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Note:
The initial states of optimal arrangements for the first example are shown in the figure below.

The initial states of optimal arrangements for the second example are shown in the figure below.

The initial states of optimal arrangements for the third example are shown in the figure below.

Example input:
3 10
abcabcabca

Example output:
19
2

Example input:
4 20
bcbcbcbcadadadadcbda

Example output:
40
2

Editorial:
First, let's solve the task for the case of linear arrangement of letters instead of a circle. Then we will upgrade the solution.
Let $$$c(x, y)$$$ be the number of positions $$$i$$$ of the password string $$$s$$$ such that $$$s_i = x$$$ and $$$s_{i + 1} = y$$$. In other words, $$$c(x, y)$$$ is the number of times Lara has to enter letter $$$y$$$ after entering letter $$$x$$$. We need to find any permutation of letters $$$p_0, p_1, p_2, \ldots, p_{k-1}$$$ of minimum cost. Integer $$$p_i$$$ stands for the index of the letter that will be placed at position $$$i$$$. The cost of a permutation is computed as $$$w(p) = \sum_{0 \leq i, j < k, i \ne j} c(p_i, p_j) \cdot |i - j|$$$.
Pointwise weights are much more convenient to use rather than pairwise weights. Re-write the cost function as follows. $$$$$$w(p) = \sum_{0 \leq i, j < k, i \ne j} c(p_i, p_j) \cdot |i - j| = \sum_{0 \leq i < j < k} (c(p_i, p_j) + c(p_j, p_i)) \cdot (j - i) = \sum_{i = 0}^{i < k} i \cdot (\sum_{j = 0}^{j < i} (c(p_j, p_i) + c(p_i, p_j)) - \sum_{j = i + 1}^{j < k} (c(p_j, p_i) + c(p_i, p_j)))$$$$$$
Usage of pointwise weights allows us to obtain the permutation step by step from left to right. When we place the new element $$$x$$$ we only need to know the subset of all already placed elements and the optimal cost of the prefix.
Define $$$d(mask)$$$ as the minimum total cost of a permutation prefix containing first $$$|mask|$$$ elements. The update function looks as follows. $$$$$$d(mask) = \min_{x \in mask} (d(mask - x) + |mask| \cdot (\sum_{y \in mask, y \ne x} (c(y, x) + c(x, y)) - \sum_{y \not\in mask} (c(y, x) + c(x, y))))$$$$$$
The above solution works in $$$O(2^n \cdot n)$$$. However, in can be updated to $$$O(2^n \cdot n)$$$ with some precomputations of the sums in the formula above.
Now we need to learn how to apply the similar idea for a positioning on a circle. The cost function now looks as follows. $$$$$$w(p) = \sum_{0 \leq i, j < k, i \ne j} c(p_i, p_j) \cdot \min(|i - j|, k - |i - j|) = \sum_{i = 0}^{k - 1} pw(p, i)$$$$$$
In order to write the cost function using pointwise weights we need to distinguish between two halves. The pointwise cost of an element in the first half is: $$$$$$pw(p, i) = i \cdot \sum_{j = 0}^{j < i} (c(p_i, p_j) + c(p_j, p_i)) - i \cdot \sum_{j = i + 1}^{j \leq i + \lfloor \frac{k}{2} \rfloor} (c(p_i, p_j) + c(p_j, p_i)) + (i + n) \cdot \sum_{j = i + \lfloor \frac{k}{2} \rfloor + 1}^{k - 1} (c(p_i, p_j) + c(p_j, p_i))$$$$$$
Similarly, the poinwise cost of an element in the second half is: $$$$$$pw(p, i) = -i \cdot \sum_{j = 0}^{j < i - \lfloor \frac{k}{2} \rfloor} (c(p_i, p_j) + c(p_j, p_i)) + i \cdot \sum_{j = i - \lfloor \frac{k}{2} \rfloor}^{j < i} (c(p_i, p_j) + c(p_j, p_i)) - i \cdot \sum_{j = i + 1}^{k - 1} (c(p_i, p_j) + c(p_j, p_i))$$$$$$
The above formulas show that it makes sense to first split all elements in two parts: left and right halves of the circle. Then we will alternate steps in adding one element to the first unoccupied position of the left part, then to the first unoccupied position of the right part. This way we will always be able to compute the value of a pointwise cost function.
So we compute the dynamic programming $$$d(S, M)$$$, where $$$S$$$ is the subset identifying the way to split the set of all letters in two equal (or almost equal for the case of odd size) parts, and $$$M$$$ is the subset of already added elements. Elements $$$S \cap M$$$ are placed at the beginning of the first half and elements $$$\overline{S} \cap M$$$ are placed at the beginning of the second half.
The simpliest complexity estimation is $$$O(4^n \cdot n)$$$. However, we should consider the following optimizations.
• We only use $$$|S| = \lceil \frac{k}{2} \rceil$$$.
• We only use states such that $$$|S \cap M| = |\overline{S} \cap M|$$$ or $$$|S \cap M| = |\overline{S} \cap M| + 1$$$.
• The character $$$s_0$$$ is always located at the first sector of the code lock, so Lara doesn't have to make any moves to enter the first character of her password. Thus, we only consider $$$s_0 \in S$$$ and $$$s_0 \in M$$$.
Considering all the above optimizations we end up with only $$$82818450 \approx 83 \cdot 10^6$$$ states. The problem statement asks you to compute the number of permutations as well. That doesn't add anything to the difficulty of this dynamic programming solution and is just used to cut away all the heuristic optimizations like annealing simulation.