E. Segment Sum 详细题解

题目重述

给定区间 $[l, r]$（$1 \le l \le r < 10^{18}$）和一个整数 $k$（$1 \le k \le 10$），求区间内所有最多包含 $k$ 种不同数字的整数的和，结果对 $998244353$ 取模。

例如：$l=10, r=50, k=1$，满足条件的数有 $11,22,33,44$，和为 $110$。

核心思路

这是一道典型的数位 DP 问题。我们需要同时统计：

• 满足条件的数字的个数
• 这些数字的总和

常规数位 DP 只统计个数，但本题需要求和，因此 DP 状态需要返回一个二元组 (count, sum)。

数位 DP 状态定义

我们将数字表示成定长（最多 $18$ 位）的十进制串，允许前导零。
定义递归函数：

$$dfs(pos, mask, tight, lead)$$

• $pos$：当前处理到第几位（从高位往低位，$0$ 为最低位，$pos = len-1$ 为最高位）
• $mask$：一个 $10$ 位的二进制掩码，表示已经使用过的数字集合（mask 的第 $i$ 位为 $1$ 表示数字 $i$ 已经出现过）
• $tight$：布尔值，表示当前前缀是否与上界 $x$ 的前缀完全相同。若 tight == true，则当前位的可选数字不能超过 $x$ 的对应位；否则 $0$～$9$ 均可。
• $lead$：布尔值，表示当前是否仍处于前导零状态（即尚未遇到非零数字）。前导零不实际计入 mask，因为数字 $0$ 只在成为非前导零时才被视作一个有效数字。

返回值：pair<ll, ll>，其中 first 表示从当前状态出发，能构造出的满足最终不同数字种数 $\le k$ 的数字个数；second 表示这些数字的总和（当前位以后的部分的值，不包含高位已固定的贡献）。

递归边界

当 $pos = -1$（所有位都已处理完毕）时：

• 如果 lead == true，表示整个数字都是前导零（即数字 $0$），根据题目 $l \ge 1$，区间内不会包含 $0$，但我们允许递归过程中出现 $0$ 作为中间状态，但在边界时不应计入，故返回 {0, 0}。
• 否则，统计 mask 中 $1$ 的个数 cnt = popcount(mask)。若 cnt \le k，则当前数字合法，返回 {1, 0}（个数为 $1$，和为 $0$，因为本层未贡献任何数值位）；否则返回 {0, 0}。

转移方程

设当前位为 $pos$，其位权为 $10^{pos}$。枚举当前位上可选的数字 $d$（取值范围由 tight 决定）：

• 新的压紧标志：ntight = tight && (d == up)，其中 up 是当前位的上界
• 新的前导零标志：nlead = lead && (d == 0)
• 新的掩码：nmask = mask；如果 !nlead（即当前位不是前导零），则将 $d$ 对应的位加入掩码：nmask |= (1 << d)

递归调用 dfs(pos-1, nmask, ntight, nlead)，得到子状态返回的 (cnt, sum)。

累计当前状态的结果：

• 个数：count = (count + cnt) mod MOD
• 总和：由两部分组成
  1. 子状态已经计算出的低位的总和 sum
  2. 当前位 $d$ 对总和的贡献：$d \times 10^{pos} \times cnt$，因为每个低位数字都重复了 cnt 次。

因此：

$$sum_{\text{cur}} = (sum_{\text{sub}} + d \cdot 10^{pos} \cdot cnt) \bmod MOD $$

所有运算均在模 $998244353$ 下进行。

利用前缀和思想

题目要求区间 $[l, r]$ 的答案，我们定义函数 $solve(x)$ 返回 $[1, x]$ 内所有满足条件的数的和。则最终答案为：

$$Ans = (solve(r) - solve(l-1) + MOD) \bmod MOD$$

$solve(x)$ 通过数位 DP 实现，将 $x$ 按位拆解，从最高位开始递归。

复杂度分析

• 数字最多 $18$ 位，状态总数：$pos \times 2^{10} \times 2 \times 2 = 20 \times 1024 \times 4 \approx 8 \times 10^4$。
• 每个状态枚举 $0$～$9$ 共 $10$ 个数字，总计算量约 $8 \times 10^5$，非常快。

实现细节

• 预处理 $10^i \bmod MOD$ 的幂表 pow10[]。
• 使用记忆化搜索，dp[pos][mask][tight][lead] 存储 (count, sum)，初始化为 (-1, -1) 表示未计算。
• 注意 tight 和 lead 只有两个取值，可以直接作为数组下标；pos 最大 $18$；mask 范围 $[0, 2^{10})$。
• 由于 $k$ 在递归中需要用到，可将其设为全局变量。

关键点总结

• 数位 DP 求和：在返回 (count, sum) 的基础上，通过当前位的贡献公式合并子状态。
• 掩码记录数字：$10$ 位二进制 mask 足以表示哪些数字出现过。
• 前导零处理：避免将前导零计入有效数字集合，同时正确处理数字 $0$ 本身（本题区间从 $1$ 开始，因此 $0$ 永远不会被计入答案）。
• 模运算：每一步都对 $998244353$ 取模，最终结果为正。

该算法时间复杂度 $O(len \cdot 2^{10} \cdot 10)$，空间 $O(len \cdot 2^{10})$，完全满足 $10^{18}$ 的数据范围。