Ideone.com

fork download

copy

#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
 
const int N = 21;
const int mod = 1e9 + 7;
 
ll dp[10][N][2][2][N];
 
void solve(ll a, ll b) {
  string l = to_string(a), r = to_string(b);
  int n = max(l.size(), r.size());
  while (l.size() < n) l = '0' + l;
  while (r.size() < n) r = '0' + r;
  int tot = 0;
  for (int dig = 0; dig < 10; dig++) {
    for (int i = 0; i <= n; i++) {
      for (int x = 0; x < 2; x++) {
        for (int y = 0; y < 2; y++) {
          for (int cnt = 0; cnt <= n; cnt++) {
            dp[dig][i][x][y][cnt] = 0;
          }
        }
      }
    }
    dp[dig][0][0][0][0] = 1;
    for (int i = 0; i < n; i++) {
      for (int a = 0; a < 2; a++) {
        for (int b = 0; b < 2; b++) {
          for (int cnt = 0; cnt <= i; cnt++) {
            for (int cur = 0; cur < 10; cur++) {
              if (!a && cur < l[i] - '0') continue;
              if (!b && cur > r[i] - '0') continue;
              int na = a | (cur > l[i] - '0');
              int nb = b | (cur < r[i] - '0');
              int nct = cnt + (cur <= dig);
              dp[dig][i + 1][na][nb][nct] += dp[dig][i][a][b][cnt];
            }
          }
        }
      }
    }
    for (int a = 0; a < 2; a++) {
      for (int b = 0; b < 2; b++) {
        for (int cnt = n; cnt >= 0; cnt--) {
          if (cnt + 1 <= n) {
            dp[dig][n][a][b][cnt] += dp[dig][n][a][b][cnt + 1];
          }
        }
        for (int cnt = 0; cnt <= n; cnt++) {
          if (a | b)
            dp[dig][n][0][0][cnt] += dp[dig][n][a][b][cnt];
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    vector <ll> cnt(10);
    for (int dig = 0; dig < 10; dig++) {
      cnt[dig] = dp[dig][n][0][0][i + 1] - (dig ? dp[dig - 1][n][0][0][i + 1] : 0);
    }
    for (ll &x : cnt) {
      x %= mod;
    }
    for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        int val = (abs(i - j) * (cnt[i] * cnt[j]) % mod) % mod;
        tot += val;
        if (tot >= mod) tot -= mod;
      }
    }
  }
  cout << tot << '\n';
}
 
int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    ll l, r;
    cin >> l >> r;
    solve(l, r);
  }
}

I2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8ZGVxdWU+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDx1bm9yZGVyZWRfbWFwPgojaW5jbHVkZSA8dW5vcmRlcmVkX3NldD4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8Y3N0cmluZz4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCiNpZmRlZiBpcQogIG10MTk5Mzcgcm5kKDIyOCk7CiNlbHNlCiAgbXQxOTkzNyBybmQoY2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpKTsKI2VuZGlmCgpjb25zdCBpbnQgTiA9IDIxOwpjb25zdCBpbnQgbW9kID0gMWU5ICsgNzsKCmxsIGRwWzEwXVtOXVsyXVsyXVtOXTsKCnZvaWQgc29sdmUobGwgYSwgbGwgYikgewogIHN0cmluZyBsID0gdG9fc3RyaW5nKGEpLCByID0gdG9fc3RyaW5nKGIpOwogIGludCBuID0gbWF4KGwuc2l6ZSgpLCByLnNpemUoKSk7CiAgd2hpbGUgKGwuc2l6ZSgpIDwgbikgbCA9ICcwJyArIGw7CiAgd2hpbGUgKHIuc2l6ZSgpIDwgbikgciA9ICcwJyArIHI7CiAgaW50IHRvdCA9IDA7CiAgZm9yIChpbnQgZGlnID0gMDsgZGlnIDwgMTA7IGRpZysrKSB7CiAgICBmb3IgKGludCBpID0gMDsgaSA8PSBuOyBpKyspIHsKICAgICAgZm9yIChpbnQgeCA9IDA7IHggPCAyOyB4KyspIHsKICAgICAgICBmb3IgKGludCB5ID0gMDsgeSA8IDI7IHkrKykgewogICAgICAgICAgZm9yIChpbnQgY250ID0gMDsgY250IDw9IG47IGNudCsrKSB7CiAgICAgICAgICAgIGRwW2RpZ11baV1beF1beV1bY250XSA9IDA7CiAgICAgICAgICB9CiAgICAgICAgfQogICAgICB9CiAgICB9CiAgICBkcFtkaWddWzBdWzBdWzBdWzBdID0gMTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgIGZvciAoaW50IGEgPSAwOyBhIDwgMjsgYSsrKSB7CiAgICAgICAgZm9yIChpbnQgYiA9IDA7IGIgPCAyOyBiKyspIHsKICAgICAgICAgIGZvciAoaW50IGNudCA9IDA7IGNudCA8PSBpOyBjbnQrKykgewogICAgICAgICAgICBmb3IgKGludCBjdXIgPSAwOyBjdXIgPCAxMDsgY3VyKyspIHsKICAgICAgICAgICAgICBpZiAoIWEgJiYgY3VyIDwgbFtpXSAtICcwJykgY29udGludWU7CiAgICAgICAgICAgICAgaWYgKCFiICYmIGN1ciA+IHJbaV0gLSAnMCcpIGNvbnRpbnVlOwogICAgICAgICAgICAgIGludCBuYSA9IGEgfCAoY3VyID4gbFtpXSAtICcwJyk7CiAgICAgICAgICAgICAgaW50IG5iID0gYiB8IChjdXIgPCByW2ldIC0gJzAnKTsKICAgICAgICAgICAgICBpbnQgbmN0ID0gY250ICsgKGN1ciA8PSBkaWcpOwogICAgICAgICAgICAgIGRwW2RpZ11baSArIDFdW25hXVtuYl1bbmN0XSArPSBkcFtkaWddW2ldW2FdW2JdW2NudF07CiAgICAgICAgICAgIH0KICAgICAgICAgIH0KICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIGZvciAoaW50IGEgPSAwOyBhIDwgMjsgYSsrKSB7CiAgICAgIGZvciAoaW50IGIgPSAwOyBiIDwgMjsgYisrKSB7CiAgICAgICAgZm9yIChpbnQgY250ID0gbjsgY250ID49IDA7IGNudC0tKSB7CiAgICAgICAgICBpZiAoY250ICsgMSA8PSBuKSB7CiAgICAgICAgICAgIGRwW2RpZ11bbl1bYV1bYl1bY250XSArPSBkcFtkaWddW25dW2FdW2JdW2NudCArIDFdOwogICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBmb3IgKGludCBjbnQgPSAwOyBjbnQgPD0gbjsgY250KyspIHsKICAgICAgICAgIGlmIChhIHwgYikKICAgICAgICAgICAgZHBbZGlnXVtuXVswXVswXVtjbnRdICs9IGRwW2RpZ11bbl1bYV1bYl1bY250XTsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICB9CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgIHZlY3RvciA8bGw+IGNudCgxMCk7CiAgICBmb3IgKGludCBkaWcgPSAwOyBkaWcgPCAxMDsgZGlnKyspIHsKICAgICAgY250W2RpZ10gPSBkcFtkaWddW25dWzBdWzBdW2kgKyAxXSAtIChkaWcgPyBkcFtkaWcgLSAxXVtuXVswXVswXVtpICsgMV0gOiAwKTsKICAgIH0KICAgIGZvciAobGwgJnggOiBjbnQpIHsKICAgICAgeCAlPSBtb2Q7CiAgICB9CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDEwOyBpKyspIHsKICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCAxMDsgaisrKSB7CiAgICAgICAgaW50IHZhbCA9IChhYnMoaSAtIGopICogKGNudFtpXSAqIGNudFtqXSkgJSBtb2QpICUgbW9kOwogICAgICAgIHRvdCArPSB2YWw7CiAgICAgICAgaWYgKHRvdCA+PSBtb2QpIHRvdCAtPSBtb2Q7CiAgICAgIH0KICAgIH0KICB9CiAgY291dCA8PCB0b3QgPDwgJ1xuJzsKfQoKaW50IG1haW4oKSB7CiNpZmRlZiBpcQogIGZyZW9wZW4oImEuaW4iLCAiciIsIHN0ZGluKTsKI2VuZGlmCiAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgY2luLnRpZSgwKTsKICBpbnQgdDsKICBjaW4gPj4gdDsKICB3aGlsZSAodC0tKSB7CiAgICBsbCBsLCByOwogICAgY2luID4+IGwgPj4gcjsKICAgIHNvbHZlKGwsIHIpOwogIH0KfQ==

Runtime error #stdin #stdout 0.98s 4260KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/09KLEl

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language