状态计算方面
设f[i][j][a][b]
下的数为:$AX…X$,即在前面加了一位$A$。
1.数量
前面所有合法方案相加即可。
下面两种情况都是在前面的数的基础上,加上一位$A$。
$$AX…X = A \times power[i - 1] + X…X$$
2.数的和
$$A * power[i - 1] * cnt + (X…X)$$
3.平方和计算
平方展开:
$$(A \times power[i - 1])^2 * cnt + (X…X)^2 + 2 \times (A \times power[i - 1]) \times (X…X)$$
因为存的是数的集合,所以在$+A * power[i - 1]$时,加了cnt
个$A$。则需要乘上集合里的数的个数。
代码
#include<iostream>
#include<vector>
using namespace std;
const int N = 20, P = 1e9 + 7;
typedef long long LL;
struct F
{
int s0, s1, s2; // 满足条件的数的 数量、和、平方和
}f[N][10][7][7]; // 一共取i位,最高位为j,数模7余a,数位和模7余b,每一位没有7的数。
int pow7[N]; // 10的i次方 模 7
LL pow9[N]; // 模 1e9 + 7
int mod(LL x, int y)
{
return (x % y + y) % y;
}
void init()
{
pow7[0] = pow9[0] = 1;
for(int i = 1; i < N; i ++)
{
pow7[i] = pow7[i - 1] * 10 % 7;
pow9[i] = pow9[i - 1] * 10 % P;
}
for(int i = 0; i <= 9; i++)
{
if(i == 7) continue;
F &v = f[1][i][i % 7][i % 7];
v.s0 ++;
v.s1 += i;
v.s2 += i * i;
}
for(int i = 2; i < N; i ++)
for(int j = 0; j <= 9; j ++)
{
if(j == 7) continue;
for(int a = 0; a < 7; a ++)
for(int b = 0; b < 7; b ++)
for(int k = 0; k <= 9; k ++)
{
F &x = f[i][j][a][b], y = f[i - 1][k][mod(a - j * pow7[i - 1], 7)][mod(b - j, 7)];
x.s0 = mod(x.s0 + y.s0, P);
x.s1 = mod(x.s1 + y.s1 + pow9[i - 1] * j % P * y.s0, P);
x.s2 = mod(x.s2 + pow9[i - 1] * pow9[i - 1] % P * j * j % P * y.s0 +
2 * j * pow9[i - 1] % P * y.s1 +
y.s2, P);
}
}
}
// 得到数 模7不为a,数位和模7不为b的 数的集合
F get(int i, int j, int a, int b)
{
int s0 = 0, s1 = 0, s2 = 0;
for(int x = 0; x < 7; x ++)
for(int y = 0; y < 7; y ++)
{
if(x == a || y == b) continue;
F v = f[i][j][x][y];
s0 = (s0 + v.s0) % P;
s1 = (s1 + v.s1) % P;
s2 = (s2 + v.s2) % P;
}
return {s0, s1, s2};
}
int dp(LL n)
{
if(!n) return 0;
LL nn = n % P;
vector<int> num;
while(n) num.push_back(n % 10), n /= 10;
n = num.size();
int ans = 0;
LL last_a = 0, last_b = 0; // 前面的数, 前面的数位和
for(int i = n - 1; i >= 0; i --)
{
int x = num[i];
for(int j = 0; j < x; j ++)
{
if(j == 7) continue;
int a = mod(-last_a * pow7[i + 1], 7); // 数模7不能为a
int b = mod(-last_b, 7); // 数位和模7不能为b
F v = get(i + 1, j, a, b);
ans = mod(ans +
last_a % P * (last_a % P) % P * pow9[i + 1] % P * pow9[i + 1] % P * v.s0 +
2 * last_a % P * pow9[i + 1] % P * v.s1 +
v.s2, P);
}
if(x == 7) break;
last_a = last_a * 10 + x;
last_b += x;
if(!i && last_a % 7 && last_b % 7) ans = mod(ans + nn * nn, P);
}
return ans;
}
int main()
{
init();
int t;
cin >> t;
while(t --)
{
LL l, r;
cin >> l >> r;
cout << mod(dp(r) - dp(l - 1), P) <<endl;
}
return 0;
}