写在前面
这两天信息量有点大，需要好好消化一下，呼呼
(f[i][j]) 的转移式还是好理解的，但是对于其实际意义课上有点糊
求 (ans_{1, x}) 是感觉手动把数拆开看会好理解一点？？
同级某巨佬wxf会用记忆化搜索做，我不会，太菜了
luoguP4999 烦人的数学作业
简述题意：
给定区间 ([ L , R ]) ,求 (L) 到 (R) 区间内每个数字和 $ (1 le L le R le 10^{18}) $ ，共 (T) 组数据 ((1 le T le 20))
Solution:
数位DP入门题？
设 (f[i][j]) ，第一维表示枚举到第 (i) 位， 第二维表示以 (j) 为最高位， (f) 数组用来存数字和
如 (f[i][j]) 中存的是 ([j000cdots , j999cdots]) 这一区间的数字和，（其中每个数都有 (i) 位）
初始状态： (f[1][i] = i (0 le i le 9))
考虑怎么转移，新枚举到的 (f[i][j]) 是在 (f[i -1][k]) 基础上加上新的一位，而因为新的一位后面可以跟 (0 - 9) 所有数，所以 (k) 的取值是 (0 - 9) ， 因为这样的数的数量是 (10^{i - 1}) 个，所以转移方程就推出来啦：
考虑最后怎么合并答案 (ans_{l, r}) ，
可以考虑先求出 (ans_{1, l}) 和 (ans_{1, r + 1}) 的答案，最后在进行合并（至于为什么是 (l) 和 (r + 1) 后面会进行解释
手模一个样例看看： (ans_{1, 114514})
发现可以将它拆开：
用 (f[i][j]) 数组一个一个代换即可，前面多出的数可以用 (sum) 存一下在循环最后处理
在每一层后面处理一下前面多出的数（感觉说不清楚，感性理解一下/kk
可以发现循环到最后一位时并不会加上最后一个数，所以将所求区间整理一下就好啦
LL solve(LL x){
LL ans = 0, sum = 0;
LL s[22], len = 0;
for(;x; x /= 10) s[++len] = x % 10;
for(int i = len; i >= 1; --i){
for(int j = 0; j < s[i]; ++j){
ans = (ans + f[i][j]) % mod;
}
ans = (ans + sum * s[i] * quick_pow(10, i - 1) % mod) % mod;
sum = (sum + s[i]) % mod;
}
return ans;
}
（一开始感觉这样写比 (Aliemo)写的简单，后来发现并没有什么本质的区别）
code：
/*
Work by: Suzt_ilymics
Knowledge: 数位DP
Time: luogu最优解第五？
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int mod = 1e9+7;
LL read(){
LL s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0', ch = getchar();
return s * w;
}
LL T, l, r, ans = 0;
LL f[22][22];
LL quick_pow(LL x, LL p){//快速幂
LL res = 1;
for( ; p; p >>= 1){
if(p & 1) res = res * x;
x = x * x;
}
return res;
}
void init(){//初始化
for(int i = 1; i <= 9; ++i) f[1][i] = i;
for(int i = 2; i <= 19; ++i){
for(int j = 0; j <= 9; ++j){
for(int k = 0; k <= 9; ++k){
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
f[i][j] = (f[i][j] + j * quick_pow(10, i - 1)) % mod;
// cout<<f[i][j]<<" ";
}
// cout<<"
";
}
}
LL solve(LL x){//求ans（1 - x）
LL ans = 0, sum = 0;
LL s[22], len = 0;
for(;x; x /= 10) s[++len] = x % 10;
for(int i = len; i >= 1; --i){
for(int j = 0; j < s[i]; ++j){
ans = (ans + f[i][j]) % mod;
}
ans = (ans + sum * s[i] * quick_pow(10, i - 1) % mod) % mod;
sum = (sum + s[i]) % mod;
}
return ans;
}
signed main()
{
init();
T = read();
while(T--){
l = read(), r = read();
printf("%lld
", (solve(r + 1) - solve(l) + mod) % mod);
}
return 0;
}
/*
in:
2
1 1000000000000000000
1 1000000000000000000
out:
3970
3970
*/