题意：给定区间[L, R]求区间内与7无关数的平方和。一个数当满足三个规则之一则认为与7有关：
1、整数中某一位是7；
2、整数的每一位加起来的和是7的整数倍；
3、这个整数是7的整数倍；
分析：初看起来确实有点麻烦，数位DP还是很容易看出来的，需要维护好三个值dp[ i ][ j ][ k ].num表示数位和为对7的余数为 j ，前面确定的数对7的余数为 k 的情况下， i 位任意与7无关的数一共有多少个；同理 dp[ i ][ j ][ k ].sum 表示这些数的和为多少；dp[ i ][ j ][ k ].sqr 表示这些数的平方和为多少，这三者之间是可以递推的，详见代码。个人觉得将区间左右边界同时代入求解更加优美。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long LL;
const int mod = int(1e9)+;
int hbit[], lbit[];
int _POW[];
struct STATUS {
int num, sum, sqr;
bool flag;
STATUS(int _num, int _sum, int _sqr) : num(_num), sum(_sum), sqr(_sqr) {}
STATUS() : flag(false) {}
// sum = sum {cur*10^p*num' + sum'}
// sqr = sum {num'*(cur*10^p)^2 + sqr' + 2*cur*10^p*sum'}
}dp[][][]; STATUS cal(int p, int srem, int mrem, bool lb, bool hb) {
if (p == ) {
if (srem != && mrem != ) return STATUS(, , );
else return STATUS(, , );
}
if (!lb && !hb && dp[p][srem][mrem].flag) {
return dp[p][srem][mrem];
}
STATUS ret(, , ), tmp;
int sta = lb ? lbit[p] : ;
int end = hb ? hbit[p] : ;
for (int i = sta; i <= end; ++i) {
if (i == ) continue;
tmp = cal(p-, (srem+i)%, (mrem*+i)%, lb&&i==sta, hb&&i==end);
ret.num = (1LL*ret.num + 1LL*tmp.num) % mod;
ret.sum = (1LL*ret.sum + 1LL*i*_POW[p-]%mod*tmp.num%mod+tmp.sum) % mod;
ret.sqr = (1LL*ret.sqr + 1LL*i*_POW[p-]%mod*i%mod*_POW[p-]%mod*tmp.num%mod + 1LL*tmp.sqr + 2LL*i*_POW[p-]%mod*tmp.sum%mod)%mod;
}
if (!lb && !hb) {
dp[p][srem][mrem] = ret;
dp[p][srem][mrem].flag = true;
}
return ret;
} int count(LL l, LL r) {
memset(lbit, , sizeof (lbit));
memset(hbit, , sizeof (hbit));
int lidx = , hidx = ;
while (l) {
lbit[lidx++] = l % ;
l /= ;
}
while (r) {
hbit[hidx++] = r % ;
r /= ;
}
return cal(max(lidx-, hidx-), , , true, true).sqr;
} int main() {
_POW[] = ;
for (int i = ; i < ; ++i) {
_POW[i] = (1LL*_POW[i-]*) % mod;
}
int T;
LL l, r;
scanf("%d", &T);
while (T--) {
scanf("%I64d %I64d", &l, &r);
printf("%d\n", count(l, r));
}
return ;
}