CF1117F Crisp String

给定一个长度为 $n$ 的字符串。字符串中的每个字符都是前 $p$ 个小写拉丁字母之一。 同时给定一个大小为 $p \times p$ 的二进制矩阵 $A$。该矩阵是对称的（即 $A_{ij} = A_{ji}$）。$A_{ij} = 1$ 表示字符串中第 $i$ 个和第 $j$ 个拉丁字母可以相邻。 如果字符串中所有相邻字符都可以相邻（即在矩阵 $A$ 的对应位置为 $1$），则称该字符串为“清脆的”。 你可以进行如下操作：任选一个字母，将其在字符串中的所有出现全部删除，并将剩余部分按原顺序拼接。例如，从 "abacaba" 中删除字母 'a'，会得到 "bcb"。 给定的字符串是清脆的。你每次操作后得到的新字符串也必须保持清脆。 你可以进行任意次数的操作（也可以不操作）。你能得到的最短字符串长度是多少？

第一行包含两个整数 $n$ 和 $p$（$1 \le n \le 10^5$，$1 \le p \le 17$），分别表示初始字符串的长度和允许使用的拉丁字母前缀长度。 第二行是初始字符串。保证字符串只包含前 $p$ 个小写拉丁字母，并且是清脆的。部分前 $p$ 个字母可能未在字符串中出现。 接下来 $p$ 行，每行包含 $p$ 个整数，表示矩阵 $A$（$0 \le A_{ij} \le 1$，$A_{ij} = A_{ji}$）。$A_{ij} = 1$ 表示第 $i$ 个和第 $j$ 个拉丁字母可以相邻。

输出一个整数，表示经过任意次数操作（可以为零）后，能得到的最短字符串长度。

在第一个样例中，不能删除任何字母。 在第二个样例中，可以依次删除字母 'b'、'c'、'a'。中间过程的字符串分别为："abacaba" $\rightarrow$ "aacaa" $\rightarrow$ "aaaa" $\rightarrow$ ""。 在第三个样例中，只能删除字母 'b'。 在第四个样例中，可以依次删除字母 'c'、'b'，但不能先删 'b' 再删 'c'，因为两个 'c' 不能相邻。 由 ChatGPT 4.1 翻译