按位DP与AC自动机：高效解决数位统计问题

数位动态规划（Dynamic Programming, DP）和AC自动机是计算机科学中两种强大的工具，常用于解决与数位统计相关的复杂问题。本文主要探讨了按位动态规划在数位统计问题中的应用，包括求解区间内具有特定性质的数的个数，例如恰好含有特定数量的某个数字、不含前导零的数、满足特定数字差分条件的数（如windy数、单峰数和双峰数）等。 按位动态规划的关键在于定义状态和状态转移方程。例如，对于区间[A,B]中恰有K个8的数的个数，可以使用一个二维数组`cnt[L][K]`来记录长度为L且恰含K个8的数的个数。状态转移规则是从最小长度开始递推，通过考虑首位、前缀以及特殊情况（如首位为0或首位已确定）来更新数组元素。 - `cnt[1][1]`初始化为1，表示只有一个数字8的数；`cnt[1][0]`为9，表示没有8的数。 - 计算区间[1-3981]中K=1的情况时，需要考虑不同位置的数字组合，如首位为1或2的数，前两位为30-38的数，等等。 状态转移方程定义为： - 对于`cnt[L][K]`，初始值为`cnt[0][0]=1`，`cnt[0][i]=0` (i>0)，后续状态通过`cnt[L][K]=cnt[L-1][K]*9+cnt[L-1][K-1]`递推，这反映了每增加一位，数位可以选择9种可能的数字（除了当前已确定的），并保持K个8不变或减少一个8。 常见问题类型的解决方案包括： 1. **求个数差**：使用两个子问题的答案相减，例如统计[0,A-1]和[0,B]的符合条件的数，然后取差值。 2. **直接统计**：针对特定性质，直接在给定区间[A,B]内计算符合条件的数的个数。 以单峰数为例，状态转移时需同时考虑数列的上界和下界限制，以及上一位置的数字，状态`dp[pos][d][u][last][state]`的含义清晰明了，有助于递归地构建所有可能的单峰数序列。 AC自动机（Aho-Corasick Automaton）在此场景下可能用来处理更复杂的模式匹配问题，但它并不直接参与按位DP的计算过程，更多用于在文本数据中高效查找多个模式。尽管如此，理解这两种技术的结合可以帮助我们更高效地解决数位相关的问题。 按位动态规划是解决数位统计问题的强大工具，它能够通过状态转移和递推策略有效地计算区间内的数的个数或满足特定条件的数，而AC自动机则提供了另一种处理字符串搜索和模式匹配的高效方法。在实际编程中，根据具体问题的特点灵活运用这两种技术，可以大大提高问题的求解效率。