一、思路分析
这题先写搜索,再加上记忆化, 难点在于数据范围很大, 处理不好的话很容易超过\(LL\)范围出错,所以记得到处取 \(MOD\)。
以一个\(6\)位数举例:
假设对于一个\(6\)位数 \(axxxxx\)
我们想知道以\(a\)开头的满足要求的\(6\)位数的平方和,(将抽象问题具体化,方便我们理解,理解清楚后,再将具体问题抽象化,方便推导)
我们不妨设\(a\)右侧的\(5\)位形成的数字为\(b\)
(给一个例子,方便理解\(a\),\(b\)是啥, 比如对于一个\(6\)位数\(213456\),\(a\)就是\(2\), \(b\)就是\(13456\)
形成的平方为 \((a * 10^5 + b)^2 = a^2 * 10^5 * 10^5 + b^2 + 2ab* 10^5\)
那么对于右侧不同的数字\(b\), 比如\(b_1\)
形成的平方\(= a^2 * 10^5 * 10^5 + b_1^2 + 2ab_1* 10^5\)
假设\(ab\),\(ab_1\),\(ab_2\),\(ab_3\), … 都是满足要求的数字
那么(ab)^2 + (ab1)^2+ (ab2)^2+ … = (a^2 * 10^5 * 10^5) * cnt + 2 * a * 10^5 * (b+b1+b2+…) + (b2+b12+b2^2…)
cnt为满足要求的数字个数, 10的多少次方可以根据数字长度预处理出来。
那么我们可以看出来
只要我们能获取满足要求的数字个数, 以及右侧所有b之和, 以及所有b^2之和 就能求出答案
所以我们dp数组类型定义成一个结构体,分别存长度,右侧数字之和, 右侧数字平方和这3项即可,
再就是状态划分了,长度缩短即可划分
二、实现代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;//要求对结果进行模1e9+7
const int N = 20; //L,R是18位的十进制数,数位最长开到20,肯定够了
const int M = 10; //因为需要记录%7的状态,所以开到10就够了
int a[N]; //数位分离的每一位结果
LL pw[N]; //(10的i次幂)%MOD
struct Node {
LL cnt; //符合要求的数字个数
LL sum; //每个数位数字和%7的值
LL sq_sum; //平方和%MOD的值
} dp[N][M][M];
//dp[i][j][k]表示从i位开始往后,最左侧到i位每位的数之和%7=j, 最左侧到i位的数%7=k
/**
比如:原数 1234567
pos 6543210
假如现在pos=3,那么dp[i=3][j=10%7=3][k=1234%7]=统计好结构体Node (Node里有三个属性:)
*/
//当前在第pos位,最高位到第pos位每位数字之和(%7)为sum,整个数字(%7)为num,limit表示是否贴合上界
Node dfs(int pos, int sum, int num, bool limit) {
//数字已填完,根据题目要求,若sum和num都不为0(不能被7整除),则贡献值++
if (pos == -1) return (Node) {sum && num, 0, 0};
//记忆化,如果不贴合上界(!lim),直接放回记录过的答案
if (!limit && ~dp[pos][sum][num].cnt) return dp[pos][sum][num];
//第pos位最大能填的数
int up = limit ? a[pos] : 9;
//声明一个结果变量,用来装本轮的结果值
Node res = {0, 0, 0};
for (int i = 0; i <= up; i++) //枚举第pos位填的数
if (i != 7) { //题目要求,数位上没有7
Node t = dfs(pos - 1, (sum + i) % 7, (num * 10 + i) % 7, limit && i == up);
//k:当前层的基值
LL k = i * pw[pos];
res.cnt = (res.cnt + t.cnt % MOD) % MOD; //统计与7无关数出现次数
res.sum = (t.cnt * k % MOD + t.sum % MOD + res.sum) % MOD;
res.sq_sum = (res.sq_sum + t.cnt * k % MOD * k % MOD + t.sq_sum + 2 * t.sum % MOD * k % MOD) % MOD;
}
return limit ? res : dp[pos][sum][num] = res;
}
LL calc(LL x) {
int pos = 0;
memset(dp, -1, sizeof dp);
while (x)a[pos++] = x % 10, x /= 10;
return dfs(pos - 1, 0, 0, 1).sq_sum;
}
int main() {
int T;
cin >> T;
//预处理(10的幂)%MOD
pw[0] = 1;
for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 10 % MOD;
while (T--) {
LL l, r;
cin >> l >> r;
printf("%lld\n", (calc(r) - calc(l - 1) + MOD) % MOD);
}
return 0;
}