题目大意：
题解：
想到用数位dp来做，用(preSum)记录前面位的数字和(\%7)，(preMod)记录前面位的数字的值(\%7)
(cnt)表示当前状态下与(7)无关的数的个数；
(sum)表示当前状态下与(7)无关的数的和；
(sqSum)表示当前状态下与(7)无关的数的平方和。
已知上一位的(sum)，可得到当前的和为：(nextSum=i imes 10^{pos} imes cnt+sum)（(i)是当前选取的数）。
设某个数到第(i)位之前的值(num)，则到第(i)位之后值为(i imes 10^{pos} + num)，则它此时的平方为：
[(i imes 10^{pos}+num)^2 = (i imes 10^{pos})^2+2 imes i imes 10^{pos} imes num+num^2
]
所以(cnt)个数的平方和就是：
[(i imes 10^{pos})^2 imes cnt+2 imes i imes 10^{pos} imes num imes cnt+num^2 imes cnt
]
[=(i imes 10^{pos})^2 imes cnt+2 imes i imes 10^{pos} imes SUM(num)+SUM(num^2)
]
[=(i imes 10^{pos})^2 imes cnt+2 imes i imes 10^{pos} imes sum+sqSum
]
注意在运算中加入取余，因为取余的原因，可能结果为负，所以要加上(mod)再取余。
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
struct Node {
ll cnt, sum, sqSum;
} dp[20][10][10];
int digit[20];
ll Bit[20];
Node dfs(int pos, int preSum, int preMod, bool limit) {
if (pos <= 0) {
return Node{preSum && preMod, 0, false};
}
if (!limit && dp[pos][preSum][preMod].cnt != -1) { // 没限制则用记忆化搜索
return dp[pos][preSum][preMod];
}
int up = limit ? digit[pos] : 9;
Node ans = Node{0, 0, false};
for (int i = 0; i <= up; ++i) {
if (i != 7) { // 排除有7的情况
Node temp = dfs(pos - 1, (preSum + i) % 7, (preMod * 10 + i) % 7, limit && i == up);
ans.cnt = (ans.cnt + temp.cnt) % mod; // 当前状态下与7无关的数的个数
ans.sum = (ans.sum + (Bit[pos] * i % mod * temp.cnt % mod + temp.sum) % mod) % mod; // 当前状态下与7无关的数的和
ans.sqSum = ((ans.sqSum + (temp.sqSum + 2 * Bit[pos] * i % mod * temp.sum % mod) % mod) % mod + i * Bit[pos] * i % mod * Bit[pos] % mod * temp.cnt % mod) % mod; // 当前状态下与7无关的数的平方和
}
}
if (!limit) dp[pos][preSum][preMod] = ans;
return ans;
}
void init() { // 10^x
Bit[1] = 1;
for (int i = 2; i < 20; ++i) {
Bit[i] = Bit[i - 1] * 10 % mod;
}
}
int cal(ll n) {
int cnt = 0;
while (n) {
digit[++cnt] = n % 10;
n /= 10;
}
return cnt;
}
int main() {
int T;
cin >> T;
init();
memset(dp, -1, sizeof(dp));
while (T--) {
ll l, r;
cin >> l >> r;
cout << (dfs(cal(r), 0, 0, true).sqSum - dfs(cal(l - 1), 0, 0, true).sqSum + mod) % mod << endl;
}
return 0;
}