1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; int T, a[22]; long long l, r, f[22], ten[22], sum[22]; bool vis[22]; long long dfs(int p, bool limit) { if (p < 0) return 0; if (!limit && vis[p]) return f[p]; long long res = 0; int up = limit ? a[p] : 9; for (int i = 0; i <= up; i++) { res = (res + dfs(p-1, limit && i==up)) % MOD; if (limit && i==up) res = (res + i * (sum[p] + 1) % MOD) % MOD; else res = (res + i * ten[p] % MOD) % MOD; } if (!limit) vis[p] = true, f[p] = res; return res; } long long cal(long long num) { memset(vis, 0, sizeof vis); long long x = 1; for (int i = 0; i <= 18; i++, x *= 10) { sum[i] = num % x % MOD; } int p = 0; while (num) { a[p++] = num % 10; num /= 10; } return dfs(p-1, 1); } void init() { ten[0] = 1; for (int i = 1; i <= 20; i++) ten[i] = ten[i-1] * 10 % MOD; } int main() { init(); scanf("%d", &T); while (T--) { scanf("%lld%lld", &l, &r); printf("%lld\n", (cal(r) - cal(l-1) + MOD) % MOD); } return 0; }
- 1
信息
- ID
- 17
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 上传者