//不超时解法--数位DP //不遍历每个数，而是按位统计每个数字在每一位上出现的次数 //利用前缀和思想：count(a, b) = count(0, b) - count(0, a-1) #include <bits/stdc++.h> using namespace std; typedef long long ll; // 统计[1, x]中数字d出现的次数 ll count(ll x, int d) { if (x <= 0) return 0; ll res = 0; ll power = 1; ...

以37->375的动态规划为例 我们已经计算出37的各个数字出现次数 那么当37->375，有一下这些情况： 1、原1-->37中出现的数字全部*10，很容易理解，原有的15-->151、152、153……159，15由一次变为10次 2、新增了0-->9，因为原来的一位数都变成了两位数 3、原来1--37各自匹配一次0--9，那么0--9各自出现了37次 4、我们在第一步直接x10，那说明我们直接算到了379，事实上我们是375，那么6--9要各减去一次，除此之外3、7要减去4次（9-5=4）...