思路：数位dp，dp[i][j]表示到第i位，数字和%10为j，然后进行dp，注意完全匹配的情况是要+1，而其他情况是从0 到 9 都要考虑
代码：
#include#include #include #include using namespace std; int t; long long A, B, dp[20][10]; long long v[20], vn; void tra(long long num) { vn = 0; while (num) { v[++vn] = num % 10; num /= 10; } for (int i = 1; i <= vn / 2; i++) swap(v[i], v[vn - i + 1]); } long long DP(long long num) { if (num == -1) return 0; memset(dp, 0, sizeof(dp)); tra(num); int x = 0; for (int i = 1; i <= vn; i++) { for (int j = 0; j < 10; j++) { for (int k = 0; k < 10; k++) { dp[i][(j + k) % 10] += dp[i - 1][j]; } } for (int j = 0; j < v[i]; j++) { dp[i][(x + j) % 10]++; } x = (x + v[i]) % 10; } if (!x) dp[vn][0]++; return dp[vn][0]; } int main() { int cas = 0; scanf(%d, &t); while (t--) { cin >> A >> B; cout << Case # << ++cas << : ; cout << DP(B) - DP(A - 1) << endl; } return 0; }