文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P4999
D
e
s
c
r
i
p
t
i
o
n
Description
Description
求
[
L
,
R
]
[L,R]
[L,R]所有数字的所有位上面数的和，答案对
1
0
9
+
7
10^9+7
109+7取模
数据范围：
L
,
R
≤
1
0
18
L,R\leq 10^{18}
L,R≤1018
S
o
l
u
t
i
o
n
Solution
Solution
可以直接数位
d
p
dp
dp 也可以P2602 数字计数改一改 代码采用的是后者
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define mod 1000000007
using namespace std
;LL L
,R
,res
;
int a
[20],m
,T
;
LL f
[20][20];
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline LL
dfs(int rest
,int sum
,int x
,bool lead
,bool limit
)
{
if(rest
==0) return sum
;
if(lead
&&limit
==0&&f
[rest
][sum
]!=-1) return f
[rest
][sum
];
int cancse
=limit
?a
[rest
]:9;
LL res
=0;
for(register int i
=0;i
<=cancse
;i
++)
(res
+=dfs(rest
-1,sum
+((lead
||i
)&&(i
==x
)),x
,lead
||i
,limit
&&i
==cancse
))%=mod
;
if(lead
&&limit
==0) f
[rest
][sum
]=res
;
return res
;
}
inline LL
solve(LL x
,int y
)
{
m
=0;
while(x
) a
[++m
]=x
%10,x
/=10;
memset(f
,-1,sizeof(f
));
return dfs(m
,0,y
,0,1);
}
signed main()
{
T
=read();
while(T
--)
{
L
=read();R
=read();res
=0;
for(register int i
=0;i
<=9;i
++) (res
+=(solve(R
,i
)-solve(L
-1,i
)+mod
)%mod
*i
%mod
)%=mod
;
printf("%lld\n",res
);
}
}
