同类分布(Same Distribution) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <string>
using namespace std;

string s;
int targetSum;
long long memo[20][170][170];

long long dfs(int pos, int curSum, int rem, bool tight) {
    if (curSum > targetSum) return 0;
    if (pos == (int)s.size()) {
        return (curSum == targetSum && rem == 0) ? 1 : 0;
    }
    if (!tight && memo[pos][curSum][rem] != -1) return memo[pos][curSum][rem];
    int up = tight ? (s[pos] - '0') : 9;
    long long res = 0;
    for (int d = 0; d <= up; ++d) {
        if (curSum + d + 9 * ((int)s.size() - 1 - pos) < targetSum) continue;
        res += dfs(pos + 1, curSum + d, (rem * 10 + d) % targetSum, tight && (d == up));
    }
    if (!tight) memo[pos][curSum][rem] = res;
    return res;
}

long long solve(long long x) {
    if (x <= 0) return 0;
    s = to_string(x);
    int maxS = 9 * (int)s.size();
    long long ans = 0;
    for (targetSum = 1; targetSum <= maxS; ++targetSum) {
        for (int i = 0; i <= (int)s.size(); ++i) {
            for (int j = 0; j <= targetSum; ++j) {
                for (int r = 0; r < targetSum; ++r) {
                    memo[i][j][r] = -1;
                }
            }
        }
        ans += dfs(0, 0, 0, true);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long a, b;
    if (!(cin >> a >> b)) return 0;
    cout << solve(b) - solve(a - 1) << "\n";
    return 0;
}