题解

问题分析

这是一个数位动态规划 + 线段树维护的问题。我们需要计算不含子串 "13" 的数字数量，并支持区间查询和单点更新。

关键观察

1. 状态设计：使用 4 个状态来记录：

   • 是否严格小于原数（高位相等/已经更小）
   • 上一位是否为 1（避免出现 "13"）

2. 矩阵转移：每个数字位对应一个转移矩阵，表示状态之间的转移关系

3. 线段树维护：用线段树维护区间矩阵乘积，支持快速查询和更新

算法思路

自动机思想 + 矩阵乘法 + 线段树：

状态编码

状态用 2 位二进制表示：

• 高位：是否仍然等于原数（0=已更小，1=仍然相等）
• 低位：上一位是否为 1（0=不是1，1=是1）

4 个状态：00, 01, 10, 11

矩阵转移

对于每个数字位 digit，构造转移矩阵：

• 遍历当前状态 s 和下一位数字 d
• 如果仍然相等且 d > digit，不能转移
• 如果上一位是1且 d == 3，不能转移（避免 "13"）
• 计算新状态：new_s = (仍然相等 && d == digit) << 1 | (d == 1)

线段树优化

• 每个叶子节点存储对应数字位的转移矩阵
• 线段树维护区间矩阵乘积
• 支持单点修改和区间查询

核心代码逻辑

矩阵类

class matrix_t {
    // 4x4 转移矩阵
    // 构造时根据当前数字位计算所有可能的转移
    matrix_t(int digit) {
        for(int s=0; s<4; ++s) for(int d=0; d<10; ++d) {
            if((s & 2) && d > digit) continue;      // 仍然相等但数字更大，不允许
            if((s & 1) && d == 3) continue;         // 上一位是1且当前是3，不允许
            int new_s = ((s & 2) && (d == digit)) << 1 | (d == 1);
            a[s][new_s] += 1;
        }
    }
};

线段树维护

class sgt_t {
    vector<matrix_t> prod;
    // 构建：每个叶子是对应数字位的转移矩阵
    // 查询：返回区间矩阵乘积
    // 修改：更新单个数字位的矩阵
};

算法步骤

1. 初始化：读入数字串，构建线段树
2. 初始答案：查询整个区间的矩阵乘积，计算总方案数
3. 处理操作：
   • 查询：返回区间 [l,r] 的方案数
   • 更新：修改单个数字，更新对应矩阵

复杂度分析

• 矩阵乘法：$O(4^3) = O(1)$
• 线段树操作：$O(\log N)$ 每次查询/更新
• 总复杂度：$O(N + Q \log N)$

状态转移详解

从状态 s 经过数字 d 转移到 new_s：

• s & 2：是否仍然等于原数
• s & 1：上一位是否为1
• 新状态：
  • 高位：(s & 2) && (d == digit)
  • 低位：d == 1

样例验证

初始数字：560484

• 总方案数：528145 ✓

查询 [3,6]：6461

• 方案数：6228 ✓

查询 [1,3]：466

• 方案数：452 ✓

查询 [6,6]：1

• 方案数：2（0,1） ✓

算法标签

• 数位动态规划
• 矩阵快速幂
• 线段树
• 自动机状态转移
• 组合计数