Submission #74772262

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

long long MOD = 1e9 + 7;

struct Result {
    long long count_with_zero;
    long long count_without_zero;
    long long sumB_with_zero;
    long long sumB_without_zero;
};

// Memoization table: idx, is_less, is_started, has_zero, last_digit
Result memo[25][2][2][2][10];
bool visited[25][2][2][2][10];
string S;

Result solve(int idx, bool is_less, bool is_started, bool has_zero, int last_digit) {
    if (idx == (int)S.size()) {
        // Base case: we found 1 number. 
        // We categorize it by whether it has a zero.
        if (has_zero) return {1, 0, 0, 0};
        else return {0, 1, 0, 0};
    }

    if (visited[idx][is_less][is_started][has_zero][last_digit]) {
        return memo[idx][is_less][is_started][has_zero][last_digit];
    }

    Result res = {0, 0, 0, 0};
    int limit = is_less ? 9 : S[idx] - '0';

    for (int d = 0; d <= limit; d++) {
        bool next_is_less = is_less || (d < limit);
        bool next_is_started = is_started || (d > 0);
        bool next_has_zero = has_zero || (next_is_started && d == 0);
        
        Result next_res = solve(idx + 1, next_is_less, next_is_started, next_has_zero, d);
        
        long long current_diff = 0;
        if (is_started && next_is_started) {
            current_diff = abs(last_digit - d);
        }

        // 1. Update Counts
        res.count_with_zero = (res.count_with_zero + next_res.count_with_zero) % MOD;
        res.count_without_zero = (res.count_without_zero + next_res.count_without_zero) % MOD;

        // 2. Update Sums (B)
        // If we are currently "started", add the current segment's difference to the running sum
        long long diff_contribution_with = (current_diff * next_res.count_with_zero) % MOD;
        long long diff_contribution_without = (current_diff * next_res.count_without_zero) % MOD;

        res.sumB_with_zero = (res.sumB_with_zero + next_res.sumB_with_zero + diff_contribution_with) % MOD;
        res.sumB_without_zero = (res.sumB_without_zero + next_res.sumB_without_zero + diff_contribution_without) % MOD;
    }

    visited[idx][is_less][is_started][has_zero][last_digit] = true;
    return memo[idx][is_less][is_started][has_zero][last_digit] = res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> S)) return 0;

    Result final_res = solve(0, false, false, false, 0);

    // Score = (SumB of trails with 0)*2 + (SumB of trails without 0)*1
    long long total_score = (final_res.sumB_with_zero * 2) % MOD;
    total_score = (total_score + final_res.sumB_without_zero) % MOD;

    cout << total_score << endl;

    return 0;
}

Submission Info

Judge Result