1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
void (ll &x, ll y){
x += y;
if(x >= mod) x -= mod;
}
struct node{
ll cnt, sum, mul;
node(ll c = -1, ll s = -1, ll m = -1){
cnt = c;
sum = s;
mul = m;
}
}dp[20][7][7];
int num[20];
ll fac[20];
node dfs(int pos, int p, int q, bool limit){
if(pos < 0) {
if(p && q) return node{1, 0, 0};
return node{0, 0, 0};
}
if(!limit && dp[pos][p][q].cnt != -1) return dp[pos][p][q];
int e = !limit ? 9 : num[pos];
node ans = {0, 0, 0};
for(int i = 0; i <= e; i++){
if(i == 7)continue;
ll x = i * fac[pos] % mod;
node tmp = dfs(pos - 1, (p + i) % 7, (q + fac[pos] % 7 * i) % 7, limit && num[pos] == i);
add(ans.cnt, tmp.cnt);
ans.sum = (ans.sum + tmp.sum + x * tmp.cnt % mod) % mod;
ans.mul = (ans.mul + 2 * tmp.sum * x % mod + x * x % mod * tmp.cnt % mod + tmp.mul) % mod;
}
if(!limit) dp[pos][p][q] = ans;
return ans;
}
ll solve(ll x){
int pos = 0;
while(x){
num[pos++] = x % 10;
x /= 10;
}
return dfs(pos - 1, 0, 0, 1).mul;
}
int T;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> T;
fac[0] = 1;
for(int i = 1; i <= 18; i++)fac[i] = fac[i - 1] * 10;
while(T--){
ll l, r;
cin >> l >> r;
cout << ((solve(r) - solve(l - 1)) % mod + mod) % mod << 'n';
}
return 0;
}
|
近期评论