计算序列数

Question

我看到了以下无法解决的问题。什么样的算法会解决？

我们得到了一个正整数n。令 A 为长度为 n 的所有可能字符串的集合，其中字符来自集合 {1,2,3,4,5,6}，即掷 n 次骰子的结果。 A 的多少个元素至少包含以下字符串之一作为子字符串：

1, 2, 3, 4, 5, 6
1, 1, 2, 2, 3, 3
4, 4, 5, 5, 6, 6
1, 1, 1, 2, 2, 2
3, 3, 3, 4, 4, 4
5, 5, 5, 6, 6, 6
1, 1, 1, 1, 1, 1
2, 2, 2, 2, 2, 2
3, 3, 3, 3, 3, 3
4, 4, 4, 4, 4, 4
5, 5, 5, 5, 5, 5
6, 6, 6, 6, 6, 6

我想知道某种递归方法，但当我试图解决问题时却一团糟。

Answer 1

你的递归方法有什么问题，你能详细说明一下吗，无论如何这可以在 O(6^n) 中使用递归方法解决，但可以使用 dp 进行优化，因为你只需要跟踪最后 6 个元素，因此可以使用 dp 在 O ( 6 * 2^6 * n) 中完成。

rec (String cur, int step) {
   if(step == n) return 0;
   int ans = 0;
   for(char c in { '1', '2', '3', '4', '5', '6' } {
      if(cur.length < 6) cur += c
      else {
         shift(cur,1) // shift the string to the left by 1 step
         cur[5] = c // add the new element to the end of the string
      }
      if(cur in list) ans += 1 + rec(cur, step+1) // list described in the question
      else ans += rec(cur, step+1)
   }
   return ans;
}

Answer 2

我建议阅读 Aho-Corasick algorithm。这构造了一个基于一组字符串的有限状态机。（如果您的字符串列表是固定的，您甚至可以手动执行此操作。）

一旦你有了一个有限状态机（大约有 70 个状态），你应该添加一个额外的吸收状态来标记何时检测到任何字符串。

现在你的问题简化为找出 6**n 个字符串中有多少个字符串在被推过状态机后最终处于吸收状态。

您可以通过将状态机表示为矩阵来做到这一点。条目 M[i,j] 表示添加一个字母后从状态 j 到达状态 i 的方法数。

最后，您计算矩阵的 n 次幂，该矩阵应用于输入向量，该向量除对应于初始状态的位置上的 1 外全为零。吸收状态位置的数字将告诉您字符串的总数。

（您可以使用标准 matrix exponentiation algorithm 在 O(logn) 时间内生成此答案。）

计算序列数

Computing number of sequences

algorithm

combinatorics