C++(g++ 7.5.0) 解法, 执行用时: 80ms, 内存消耗: 19916K, 提交时间: 2023-07-11 13:46:02

#include <iostream>

using namespace std;

const int N = 200010;
const int mod = 1e9 + 7;

string s;

struct State {  
  int cnt, sum;
  State() = default;
  State(int cnt) : cnt(cnt) { sum = 0; }
  State operator+=(const State &oth) {
    (cnt += oth.cnt) %= mod;
    (sum += oth.sum) %= mod;
    return *this;
  }
  State operator+= (const int &k) {
    (sum += 1ll * k * cnt % mod) %= mod;
    return *this;
  }
} f[N][2];
bool vis[N][2];

State dfs(int pos, bool lim, int lst) {
  if (pos == size(s)) return lst == 8;
  State& v = f[pos][lim];
  if (vis[pos][lim]) return v;
  vis[pos][lim] = true;
  State res = 0;
  int upper = lim ? s[pos] - '0' : 9;
  for (int i = 0; i <= upper; i++) {
    bool nlim = lim and (i == s[pos] - '0');
    res += dfs(pos + 1, nlim, i) += i;
  }
  return v = res;
}


int main() {
  cin >> s;
  cout << dfs(0, true, -1).sum;
  return 0;
}

C++(clang++11) 解法, 执行用时: 16ms, 内存消耗: 5572K, 提交时间: 2021-05-13 19:15:39

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
const ll mod = 1e9 + 7;
char a[N];
ll f[N][2];
ll g[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> (a + 1);
    int n = strlen(a + 1);
    for (int i = 1; i < n; ++i) {
        int cur = a[i] - '0';
        f[i][0] = (f[i - 1][0] * 10 + g[i - 1] * 45 + f[i - 1][1] * cur + cur * (cur - 1) / 2 ) % mod;
        f[i][1] = (f[i - 1][1] + cur) % mod;
        g[i] = (g[i - 1] * 10 + cur) % mod;
    }
 
    cout << (f[n - 1][0] + g[n - 1] * 8 + (a[n] - '0' < 8 ? 0 : f[n - 1][1] + 8)) % mod;
}