思路

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

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

• 预处理定义：

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

  • 转移：

    $$ways[0][min][0]=1,\quad ways[0][min][s>0]=0$$

    

• 回答查询：

  • 设 $m$ 的长度为 $n$，其数位为 $a_0,\dots,a_{n-1}$。

  • 统计位数小于 $n$ 的升数：首位 $f\in[1,9]$，后面 $L-1$ 位用 $ways[L-1][f][\cdot]$；把该向量按 $d$ 聚合，取满足 $(f+s_R)\bmod d=0$ 的总数。

  • 统计与 $m$ 同长度的升数：逐位扫描，用当前“前缀最小允许值” $mn$ 和“前缀和模 $d$” $S$。在位置 $i$：

    • 对所有 $x\in[mn,a_i-1]$，把 $ways[n-i-1][x][\cdot]$ 按 $d$ 聚合，取满足 $(S+x+s_R)\bmod d=0$ 的总数。
    • 若 $a_i<mn$ 则无法继续等前缀，提前结束；否则令 $S\leftarrow(S+a_i)\bmod d$，$mn\leftarrow a_i$ 继续。

  • 若整段“等前缀”成功且 $S\bmod d=0$，再加 $1$（即 $m$ 自身是升数且满足模条件）。

• 复杂度：

  • 预处理规模约为 $\sum_{L=0}^{18} 10 \cdot (10) \cdot (9L+1)$，远小于 $10^6$；
  • 单次查询仅需把若干长度为 $\le 171$ 的向量按模 $d$ 聚合，约 $O(10 \cdot n \cdot 171)$ 操作，$Q$ 次查询整体在 C++/Java 轻松通过，Python 也可。

C++

#include <bits/stdc++.h>
using namespace std;

// 按给定 d 与余数 r，把 ways 向量中下标同余于 r 的项相加
static inline long long sum_by_mod(const vector<long long>& vec, int d, int r) {
	int n = (int)vec.size();
	long long ans = 0;
	for (int i = r; i < n; i += d) ans += vec[i];
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	string mstr;
	int Q;
	if (!(cin >> mstr >> Q)) return 0;
	vector<int> digits;
	for (char c : mstr) digits.push_back(c - '0');
	int n = (int)digits.size();
	
	// 预处理 ways[L][minDigit] = vector<long long>，长度为 9*L+1，存每个数位和的方案数
	int maxRem = max(0, n - 1); // 最大剩余长度
	vector<vector<vector<long long>>> ways(maxRem + 1, vector<vector<long long>>(10));
	for (int L = 0; L <= maxRem; ++L) {
		for (int mn = 0; mn <= 9; ++mn) {
			ways[L][mn].assign(9 * L + 1, 0LL);
		}
	}
	// 基础：L=0
	for (int mn = 0; mn <= 9; ++mn) ways[0][mn][0] = 1;
	// 自底向上计算
	for (int L = 1; L <= maxRem; ++L) {
		for (int mn = 0; mn <= 9; ++mn) {
			// 当前位取 x，后面 L-1 位从 ways[L-1][x] 转移
			for (int x = mn; x <= 9; ++x) {
				const vector<long long>& prev = ways[L-1][x];
				for (int sR = 0; sR < (int)prev.size(); ++sR) {
					ways[L][mn][x + sR] += prev[sR];
				}
			}
		}
	}
	
	auto solve_one = [&](int d) -> long long {
		long long ans = 0;
		// 统计位数小于 n 的升数
		for (int L = 1; L < n; ++L) {
			for (int f = 1; f <= 9; ++f) {
				const auto& vec = ways[L-1][f];
				int need = (d - (f % d)) % d;
				ans += sum_by_mod(vec, d, need);
			}
		}
		// 统计与 m 同长度的升数
		int mn = 1;        // 第一位至少为 1
		int Smod = 0;      // 前缀和模 d
		bool ok = true;    // 是否还能走“等前缀”
		for (int i = 0; i < n; ++i) {
			int bound = digits[i];
			// 在第 i 位放更小的 x
			for (int x = mn; x <= bound - 1; ++x) {
				int rem = n - i - 1;
				const auto& vec = ways[rem][x];
				int need = (d - ((Smod + x) % d)) % d;
				ans += sum_by_mod(vec, d, need);
			}
			// 尝试放等于 bound
			if (bound < mn) { ok = false; break; }
			Smod = (Smod + bound) % d;
			mn = bound;
		}
		// 如果 m 本身是升数且满足模条件
		if (ok && Smod % d == 0) ans += 1;
		return ans;
	};
	
	for (int qi = 0; qi < Q; ++qi) {
		int d; cin >> d;
		cout << solve_one(d) << "\n";
	}
	return 0;
}

Python

import sys

def sum_by_mod(vec, d, r):
    # 把 vec 中下标同余于 r 的项相加
    s = 0
    for i in range(r, len(vec), d):
        s += vec[i]
    return s

def main():
    data = sys.stdin.read().strip().split()
    mstr = data[0]
    Q = int(data[1])
    ds = list(map(int, data[2:2+Q]))
    digits = [int(c) for c in mstr]
    n = len(digits)

    maxRem = max(0, n - 1)
    ways = [[None for _ in range(10)] for __ in range(maxRem + 1)]
    for L in range(maxRem + 1):
        for mn in range(10):
            ways[L][mn] = [0] * (9 * L + 1)
    for mn in range(10):
        ways[0][mn][0] = 1
    for L in range(1, maxRem + 1):
        for mn in range(10):
            cur = ways[L][mn]
            for x in range(mn, 10):
                prev = ways[L-1][x]
                # 卷积式转移：把 x 加到每个 sR
                for sR, cnt in enumerate(prev):
                    cur[x + sR] += cnt

    def solve_one(d):
        ans = 0
        # 位数小于 n
        for L in range(1, n):
            for f in range(1, 10):
                vec = ways[L-1][f]
                need = (-f) % d
                ans += sum_by_mod(vec, d, need)
        # 位数等于 n
        mn = 1
        Smod = 0
        ok = True
        for i, bound in enumerate(digits):
            for x in range(mn, bound):
                rem = n - i - 1
                vec = ways[rem][x]
                need = (-(Smod + x)) % d
                ans += sum_by_mod(vec, d, need)
            if bound < mn:
                ok = False
                break
            Smod = (Smod + bound) % d
            mn = bound
        if ok and Smod % d == 0:
            ans += 1
        return ans

    out = []
    for d in ds:
        out.append(str(solve_one(d)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
	static long sumByMod(long[] vec, int d, int r) {
		long ans = 0;
		for (int i = r; i < vec.length; i += d) ans += vec[i];
		return ans;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		String mstr = st.nextToken();
		int Q = Integer.parseInt(st.nextToken());
		int[] queries = new int[Q];
		for (int i = 0; i < Q; i++) {
			queries[i] = Integer.parseInt(br.readLine().trim());
		}
		int n = mstr.length();
		int[] digits = new int[n];
		for (int i = 0; i < n; i++) digits[i] = mstr.charAt(i) - '0';
		
		int maxRem = Math.max(0, n - 1);
		long[][][] ways = new long[maxRem + 1][10][];
		for (int L = 0; L <= maxRem; L++) {
			for (int mn = 0; mn <= 9; mn++) {
				ways[L][mn] = new long[9 * L + 1];
			}
		}
		for (int mn = 0; mn <= 9; mn++) ways[0][mn][0] = 1;
		for (int L = 1; L <= maxRem; L++) {
			for (int mn = 0; mn <= 9; mn++) {
				long[] cur = ways[L][mn];
				for (int x = mn; x <= 9; x++) {
					long[] prev = ways[L - 1][x];
					for (int sR = 0; sR < prev.length; sR++) {
						cur[x + sR] += prev[sR];
					}
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int qi = 0; qi < Q; qi++) {
			int d = queries[qi];
			long ans = 0;
			// 位数小于 n
			for (int L = 1; L < n; L++) {
				for (int f = 1; f <= 9; f++) {
					long[] vec = ways[L - 1][f];
					int need = ((d - (f % d)) % d);
					ans += sumByMod(vec, d, need);
				}
			}
			// 位数等于 n
			int mn = 1;
			int Smod = 0;
			boolean ok = true;
			for (int i = 0; i < n; i++) {
				int bound = digits[i];
				for (int x = mn; x <= bound - 1; x++) {
					int rem = n - i - 1;
					long[] vec = ways[rem][x];
					int need = (d - ((Smod + x) % d)) % d;
					ans += sumByMod(vec, d, need);
				}
				if (bound < mn) { ok = false; break; }
				Smod = (Smod + bound) % d;
				mn = bound;
			}
			if (ok && Smod % d == 0) ans += 1;
			sb.append(ans).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

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

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

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

【名词解释】

• 升数：升数 是其十进制表示中，除首位外每个数字不小于其左侧相邻数字的正整数。

输入描述

第一行输入两个整数 $m,Q(1≤m ≤ 10^{18},1≤Q≤ 500)$，分别表示上限和查询次数。

接下来 $Q$ 行，每行输入一个整数 $d(1 ≤d≤ 200)$ ，表示查询的模数。

输出描述

输出 $Q$ 行，第 $i$ 行输出一个整数，表示所有小于等于 $m$ 的升数中，数位和对 $d_i$ 取模为 $0$ 的个数。

样例1

输入

50 2
1
10

输出

39
4

说明

从 $1$ 到 $50$ 中，升数一共有 $39$ 个，其中数位和模 $10$ 等于 $0$ 的一共有 $4$ 个，分别是 $19,28,37,46$ 。

样例2

输入

100 3
3
4
7

输出

18
14
7