AcWing 1086 恨7不是妻
题目传送门
一、思路分析
这题先写搜索,再加上记忆化, 难点在于数据范围很大, 处理不好的话很容易超过\(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 + (ab_1)^2+ (ab_2)^2+ … = (a^2 * 10^5 * 10^5) *cnt+2 * a * 10^5 * (b+b_1+b_2+…) + (b^2+b_1^2+b_2^2…)\)
其中
- \(\large cnt\)为满足要求的数字个数
- \(10\)的多少次方可以根据数字长度预处理出来。
那么我们可以看出来
只要我们能获取
- 满足要求的数字个数
- 右侧所有\(b\)之和
- 右侧所有\(b^2\)之和
就能求出答案！
所以我们\(dp\)数组类型定义成一个结构体，分别存满足要求的数字个数，右侧数字之和, 右侧数字平方和这\(3\)项即可，再就是状态划分了，长度缩短即可划分。
二、实现代码
#include
using namespace std;
typedef long long LL;
const LL P = 1e9 + 7; //要求对结果进行模1e9+7
const LL N = 20; //L,R是18位的十进制数，数位最长开到20，肯定够了
const LL M = 10; //因为需要记录%7的状态，所以开到10就够了
LL a[N]; //数位分离的每一位结果
LL pw[N]; //(10的i次幂)%P
//依赖于递归进行填充
struct Node {
LL cnt; //表示与7无关的数的个数
LL sum; //表示所有与7无关的数的和
LL sq_sum; //表示所有与7无关的数的平方和
} dp[N][M][M];
/*
dp[i][sum][num]含义：
第一维度：i,表示当前数位位置是i
第二维度：从第i位开始，最高位到第i位每位数字之和（%7）为sum，只有记录了这个信息，后面才好判断加上自己的数位，是不是数字和%7=0
第三维度：整个数字（%7）为num 如对于数123***，i=2时，sum=6，num=123 (i从0开始) 注意:这个num 需要乘10才能进行递推~
*/
//当前在第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];
//统计与7无关数出现次数
(res.cnt += t.cnt) %= P;
/*
统计所有与7无关数的和（用dfs（i-1）已经求出了所有无关数第i-1位到最后一位所组成的数之和，即t.sum，
再加上第i位即可，即t.cnt*k）
例如i=5，已知无关数有**61111，**62222，**63333（随便瞎写的几个数字）
则k=60000，t.sum=1111+2222+3333，t.cnt=3，res.sum=61111+62222+63333
*/
(res.sum += t.sum + t.cnt * k) %= P;
/*
统计所有与7无关数第i位到最后一位所组成的数的平方和
例如i=5，已知无关数有**61111，**62222，**63333（随便瞎写的几个数字）
对于61111^2=(60000+1111)^2=(60000)^2+(1111)^2+2*60000*1111
62222,63333同理
则res.sq_sum=61111^2+62222^2+63333^2
=3*(60000)^2 + (1111^2+2222^2+3333^2) + 2*60000*(1111+2222+3333)
=t.cnt*k*k + t.sq_sum + 2*k*t.sum
可以发现，我们用后i-1位的sq_sum即可推算出后i位的sq_sum
*/
(res.sq_sum += t.cnt * k % P * k % P + t.sq_sum + 2 * t.sum % P * k % P) %= P;
}
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 % P;
while (T--) {
LL l, r;
cin >> l >> r;
printf("%lld\n", (calc(r) - calc(l - 1) + P) % P);
}
return 0;
}