题目理解

我们需要找到所有满足以下条件的正整数：

1. 数字之和等于 $s$
2. 能被 $m$ 整除
3. 按数值从小到大排序

然后回答 $q$ 个查询，每个查询要求第 $k_i$ 小的满足条件的数。

关键观察

1. 数位DP思想

这是一个典型的数位计数问题，需要统计满足条件的数字数量。

2. 状态设计

使用三维DP：

• 第1维：数字长度（最多200位）
• 第2维：当前数字和
• 第3维：当前数值模 $m$ 的余数

算法核心

动态规划预处理

vector<vector<vector<int64_t>>> dp(
    201, vector<vector<int64_t>>(
        s + 1, vector<int64_t>(m, 0)
    )
);
dp[0][0][0] = 1;  // 初始状态：长度为0，和为0，余数为0

for (int i = 0; i < 200; ++i)
    for (int j = 0; j <= s; ++j)
        for (int k = 0; k < m; ++k)
            if (dp[i][j][k])
                for (int x = 0; x < 10 && j + x <= s; ++x)
                    Inc(dp[i + 1][j + x][(10 * k + x) % m], dp[i][j][k]);

DP状态转移：

• dp[len][sum][mod] 表示长度为 len，数字和为 sum，模 $m$ 余数为 mod 的数字数量
• 从长度 len 转移到 len+1，枚举下一位数字 x (0-9)
• 新的余数 = (10 * mod + x) % m
• 新的数字和 = sum + x

查询处理

// 预处理10的幂次模m
for (int i = pw[0] = 1; i <= 200; ++i)
    pw[i] = pw[i - 1] * 10 % m;

// 从高位到低位确定每一位
for (int i = 200, j = s, k = 0; i >= 1; --i) {
    int x = 0;
    // 尝试当前位放数字x，计算剩余数量
    while (x < 10 && t > (tmp = dp[i - 1][j - x][(k - pw[i - 1] * x % m + m) % m])) {
        t -= tmp;
        x += 1;
    }
    j -= x;
    k = (k - pw[i - 1] * x % m + m) % m;
    
    if (to_print || x > 0) {
        to_print = true;
        putchar(x + '0');
    }
}

算法正确性

1. DP状态设计

• 长度维度：最多200位，符合题目限制
• 数字和维度：不超过 $s \leq 500$
• 余数维度：模 $m \leq 500$

2. 查询构造

从高位到低位逐位确定：

• 对于当前位，尝试数字0-9
• 计算如果当前位放数字x，剩余位数能构成多少满足条件的数
• 如果剩余数量足够，就选择当前数字，否则尝试更大的数字

3. 边界处理

• 如果 $t > dp[200][s][0]$，说明第 $t$ 小的数超过200位或不存在
• 前导零处理：只有当出现非零数字后才开始输出

时间复杂度

预处理阶段

• DP状态数：$200 \times 500 \times 500 = 5 \times 10^7$
• 每个状态最多10次转移
• 总操作数：$5 \times 10^8$，在合理范围内

查询阶段

• 每个查询最多 $200 \times 10 = 2000$ 次操作
• $q \leq 10^6$ 时，总操作数 $2 \times 10^9$，需要优化实现

关键优化

1. 数值范围控制

inline void Inc(int64_t &x, int64_t y) {
    x += y;
    if (x > MAX)  // MAX = 10^18
        x = MAX + 1;
}

• 避免大整数运算
• 当数量超过 $10^{18}$ 时直接截断

2. 模运算优化

预处理10的幂次模 $m$，避免重复计算。

算法标签

• 数位动态规划
• 计数问题
• 模运算
• 大数处理

特殊情况处理

1. 前导零

在构造数字时，只有当出现非零数字后才开始输出，正确处理了前导零问题。

2. 不存在情况

当 $t > dp[200][s][0]$ 时，说明第 $t$ 小的数不存在或超过200位。

3. 数值范围

使用 int64_t 并设置上限，避免溢出。

总结

该算法通过巧妙的数位DP预处理，高效统计了满足条件的数字数量，然后通过贪心构造找到第 $k$ 小的数。核心思想是利用动态规划预处理所有可能状态的数量，然后在线回答查询。算法设计精妙，在严格的时间限制下解决了大规模查询问题。