思路

• 核心是数位 DP，带“非严格单调约束”和“数位和按模取值”的统计。

• 为了应对多达 $Q=500$ 次不同 $d$ 的查询，直接把 $d$ 放入 DP 状态会在 Python 中偏慢。优化思路：把“模运算”延后，用“数位和分布向量”预处理，然后对每个 $d$ 再按模聚合。

• 预处理定义：

  • 设 $ways[L][min][s]$ 表示长度为 $L$ 的非降序数字序列（允许前导零，但当前位必须 $\ge min$），其数位和为 $s$ 的方案数。

  • 转移：

    $$$$

题目内容

我们称一个正整数为"升数"，当且仅当其十进制表示的各位数字从高位到低位单调不降(例如 $1123、5$ )。

给定一个正整数 $m$ 和查询次数 $Q$ 。每个查询给出一个正整数 $d$ 。

请统计所有不超过 $m$ 的升数中，数位之和能被 $d$ 整除的升数个数。

【名词解释】