Ideone.com

fork download

copy

#include <bits/stdc++.h>
 
using namespace std;
 
#define int int64_t
#define all(x) begin(x), end(x)
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int mod = 1e9 + 7;
const int maxn = 30;
 
template<typename T>
T bpow(T x, int n) {
	return n ? n % 2 ? x * bpow(x, n - 1) : bpow(x * x, n / 2) : T(1);
}
 
struct base {
	int r;
	base():r(0){}
	base(int r):r((r % mod + mod) % mod){}
	base operator += (base t) {r = (r + t.r) % mod; return *this;}
	base operator *= (base t) {r = (r * t.r) % mod; return *this;}
	base operator -= (base t) {r = (r - t.r + mod) % mod; return *this;}
	base inv() {return bpow(*this, mod - 2);}
	base operator /= (base t) {return *this *= t.inv();}
	base operator + (base t) const {return base(*this) += t;}
	base operator - (base t) const {return base(*this) -= t;}
	base operator * (base t) const {return base(*this) *= t;}
	base operator / (base t) const {return base(*this) /= t;}
};
 
base F[maxn];
base fact(int n) {
	return F[n].r ? F[n] : n ? F[n] = fact(n - 1) * n : base(1);
}
 
base T[maxn][maxn][maxn];
base trinom(int a, int b, int c) {
	return min({a, b, c}) < 0 ? 0 : T[a][b][c].r ? T[a][b][c] : max({a, b, c}) > 0 ? T[a][b][c] = trinom(a - 1, b, c) + trinom(a, b - 1, c) + trinom(a, b, c - 1) : 1;
}
 
const int l = 20;
map<tuple<int, int, int>, base> memo;
base get(int i, int j, int A) {
	if(memo.count({i, j, A})) {
		return memo[{i, j, A}];
	} else {
		string s = to_string(A);
		s = string(l - s.size(), '0') + s;
		base res = 0;
		int cnt_le = 0;
		int cnt_eq = 0;
		for(int t = 0; t < l; t++) {
			for(int d = 0; d < s[t] - '0'; d++) {
				for(int a = 0; a <= l - (t + 1); a++) {
					for(int b = 0; a + b <= l - (t + 1); b++) {
						int c = l - (t + 1) - a - b;
						int cur_le = cnt_le + (d < j) + a;
						int cur_eq = cnt_eq + (d == j) + c;
						if(cur_le <= i && cur_le + cur_eq > i) {
							base mulA = bpow(base(j), a) * bpow(base(10 - j - 1), b);
							base mulB = trinom(a, b, c);
							res += mulA * mulB;
						}
					}
				}
			}
			cnt_le += (s[t] - '0') < j;
			cnt_eq += (s[t] - '0') == j;
		}
		sort(all(s));
		return memo[{i, j, A}] = res + (s[i] - '0' == j);
	}
}
 
base sum(int a, int b) {
	base E = 0;
	for(int i = 0; i < l; i++) {
		for(int j = 0; j <= 9; j++) {
			for(int k = 0; k <= 9; k++) {
				E += get(i, j, a) * get(i, k, b) * abs(j - k);
			}
		}
	}
	return E;
}
 
void solve() {
	int L, R;
	cin >> L >> R;
	cout << (sum(R, R) - sum(L - 1, R) * 2 + sum(L - 1, L - 1)).r << endl;
}
 
signed main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBpbnQgaW50NjRfdAojZGVmaW5lIGFsbCh4KSBiZWdpbih4KSwgZW5kKHgpCgptdDE5OTM3XzY0IHJuZyhjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwoKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CmNvbnN0IGludCBtYXhuID0gMzA7Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPgpUIGJwb3coVCB4LCBpbnQgbikgewoJcmV0dXJuIG4gPyBuICUgMiA/IHggKiBicG93KHgsIG4gLSAxKSA6IGJwb3coeCAqIHgsIG4gLyAyKSA6IFQoMSk7Cn0KCnN0cnVjdCBiYXNlIHsKCWludCByOwoJYmFzZSgpOnIoMCl7fQoJYmFzZShpbnQgcik6cigociAlIG1vZCArIG1vZCkgJSBtb2Qpe30KCWJhc2Ugb3BlcmF0b3IgKz0gKGJhc2UgdCkge3IgPSAociArIHQucikgJSBtb2Q7IHJldHVybiAqdGhpczt9CgliYXNlIG9wZXJhdG9yICo9IChiYXNlIHQpIHtyID0gKHIgKiB0LnIpICUgbW9kOyByZXR1cm4gKnRoaXM7fQoJYmFzZSBvcGVyYXRvciAtPSAoYmFzZSB0KSB7ciA9IChyIC0gdC5yICsgbW9kKSAlIG1vZDsgcmV0dXJuICp0aGlzO30KCWJhc2UgaW52KCkge3JldHVybiBicG93KCp0aGlzLCBtb2QgLSAyKTt9CgliYXNlIG9wZXJhdG9yIC89IChiYXNlIHQpIHtyZXR1cm4gKnRoaXMgKj0gdC5pbnYoKTt9CgliYXNlIG9wZXJhdG9yICsgKGJhc2UgdCkgY29uc3Qge3JldHVybiBiYXNlKCp0aGlzKSArPSB0O30KCWJhc2Ugb3BlcmF0b3IgLSAoYmFzZSB0KSBjb25zdCB7cmV0dXJuIGJhc2UoKnRoaXMpIC09IHQ7fQoJYmFzZSBvcGVyYXRvciAqIChiYXNlIHQpIGNvbnN0IHtyZXR1cm4gYmFzZSgqdGhpcykgKj0gdDt9CgliYXNlIG9wZXJhdG9yIC8gKGJhc2UgdCkgY29uc3Qge3JldHVybiBiYXNlKCp0aGlzKSAvPSB0O30KfTsKCmJhc2UgRlttYXhuXTsKYmFzZSBmYWN0KGludCBuKSB7CglyZXR1cm4gRltuXS5yID8gRltuXSA6IG4gPyBGW25dID0gZmFjdChuIC0gMSkgKiBuIDogYmFzZSgxKTsKfQoKYmFzZSBUW21heG5dW21heG5dW21heG5dOwpiYXNlIHRyaW5vbShpbnQgYSwgaW50IGIsIGludCBjKSB7CglyZXR1cm4gbWluKHthLCBiLCBjfSkgPCAwID8gMCA6IFRbYV1bYl1bY10uciA/IFRbYV1bYl1bY10gOiBtYXgoe2EsIGIsIGN9KSA+IDAgPyBUW2FdW2JdW2NdID0gdHJpbm9tKGEgLSAxLCBiLCBjKSArIHRyaW5vbShhLCBiIC0gMSwgYykgKyB0cmlub20oYSwgYiwgYyAtIDEpIDogMTsKfQoKY29uc3QgaW50IGwgPSAyMDsKbWFwPHR1cGxlPGludCwgaW50LCBpbnQ+LCBiYXNlPiBtZW1vOwpiYXNlIGdldChpbnQgaSwgaW50IGosIGludCBBKSB7CglpZihtZW1vLmNvdW50KHtpLCBqLCBBfSkpIHsKCQlyZXR1cm4gbWVtb1t7aSwgaiwgQX1dOwoJfSBlbHNlIHsKCQlzdHJpbmcgcyA9IHRvX3N0cmluZyhBKTsKCQlzID0gc3RyaW5nKGwgLSBzLnNpemUoKSwgJzAnKSArIHM7CgkJYmFzZSByZXMgPSAwOwoJCWludCBjbnRfbGUgPSAwOwoJCWludCBjbnRfZXEgPSAwOwoJCWZvcihpbnQgdCA9IDA7IHQgPCBsOyB0KyspIHsKCQkJZm9yKGludCBkID0gMDsgZCA8IHNbdF0gLSAnMCc7IGQrKykgewoJCQkJZm9yKGludCBhID0gMDsgYSA8PSBsIC0gKHQgKyAxKTsgYSsrKSB7CgkJCQkJZm9yKGludCBiID0gMDsgYSArIGIgPD0gbCAtICh0ICsgMSk7IGIrKykgewoJCQkJCQlpbnQgYyA9IGwgLSAodCArIDEpIC0gYSAtIGI7CgkJCQkJCWludCBjdXJfbGUgPSBjbnRfbGUgKyAoZCA8IGopICsgYTsKCQkJCQkJaW50IGN1cl9lcSA9IGNudF9lcSArIChkID09IGopICsgYzsKCQkJCQkJaWYoY3VyX2xlIDw9IGkgJiYgY3VyX2xlICsgY3VyX2VxID4gaSkgewoJCQkJCQkJYmFzZSBtdWxBID0gYnBvdyhiYXNlKGopLCBhKSAqIGJwb3coYmFzZSgxMCAtIGogLSAxKSwgYik7CgkJCQkJCQliYXNlIG11bEIgPSB0cmlub20oYSwgYiwgYyk7CgkJCQkJCQlyZXMgKz0gbXVsQSAqIG11bEI7CgkJCQkJCX0KCQkJCQl9CgkJCQl9CgkJCX0KCQkJY250X2xlICs9IChzW3RdIC0gJzAnKSA8IGo7CgkJCWNudF9lcSArPSAoc1t0XSAtICcwJykgPT0gajsKCQl9CgkJc29ydChhbGwocykpOwoJCXJldHVybiBtZW1vW3tpLCBqLCBBfV0gPSByZXMgKyAoc1tpXSAtICcwJyA9PSBqKTsKCX0KfQoKYmFzZSBzdW0oaW50IGEsIGludCBiKSB7CgliYXNlIEUgPSAwOwoJZm9yKGludCBpID0gMDsgaSA8IGw7IGkrKykgewoJCWZvcihpbnQgaiA9IDA7IGogPD0gOTsgaisrKSB7CgkJCWZvcihpbnQgayA9IDA7IGsgPD0gOTsgaysrKSB7CgkJCQlFICs9IGdldChpLCBqLCBhKSAqIGdldChpLCBrLCBiKSAqIGFicyhqIC0gayk7CgkJCX0KCQl9Cgl9CglyZXR1cm4gRTsKfQoKdm9pZCBzb2x2ZSgpIHsKCWludCBMLCBSOwoJY2luID4+IEwgPj4gUjsKCWNvdXQgPDwgKHN1bShSLCBSKSAtIHN1bShMIC0gMSwgUikgKiAyICsgc3VtKEwgLSAxLCBMIC0gMSkpLnIgPDwgZW5kbDsKfQoKc2lnbmVkIG1haW4oKSB7CgkvL2ZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOwoJaW50IHQ7CgljaW4gPj4gdDsKCXdoaWxlKHQtLSkgewoJCXNvbHZlKCk7Cgl9CglyZXR1cm4gMDsKfQ==

Time limit exceeded #stdin #stdout 5s 4184KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/nYZ7cI

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