10 KiB
AcWing 1086. 恨7不成妻
一、题目描述
单身！
依然单身！
吉哥依然单身！
DS 级码农吉哥依然单身！
所以，他平生最恨情人节，不管是 214 还是 77，他都讨厌！
吉哥观察了 214 和 77 这两个数，发现：
2+1+4=7
7+7=7×2
77=7×11
最终，他发现原来这一切归根到底都是因为和 7 有关！
所以，他现在甚至讨厌一切和 7 有关的数！
什么样的数和 7 有关呢？
如果一个整数符合下面三个条件之一，那么我们就说这个整数和 7 有关：
- ① 整数中某一位是
7； - ② 整数的每一位加起来的和是
7的整数倍； - ③ 这个整数是
7的整数倍。
现在问题来了：吉哥想知道在一定区间内 和 7 无关的整数的平方和。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据占一行，包含两个整数 L 和 R。
输出格式
对于每组数据，请计算 [L,R] 中和 7 无关的数字的平方和，并将结果对 10^9+7 取模后输出。
数据范围
1≤T≤50,1≤L≤R≤10^{18}
输入样例：
3
1 9
10 11
17 17
输出样例：
236
221
0
二、题目解析
1、递【传递信息】
这题如果只是求整数区间 [l,r] 内满足要求的数的 个数，难度可以归为 简单
我们先想一下如何求解我说的这个 简单问题
毫无疑问是用 数位DP 来求解，那么在从前向后的搜索过程中，需要 向后传递 的参数有：
-
前
u位数位上的数字之和模7的余数sum(对应题目中的②) -
前
u位模7的余数pre(对应题目中的③)
① 某个数位是不是
7，直接判断即可，不用传递。
只有前一个位置 传递 这两个信息，下一个数位才好判断自己怎么办，也就比 前5道数位DP 多了一个参数,表现在记忆化中就是数组多了一维罢了。
2、归【合并信息】
可惜本题要求的不是满足要求的 数字的个数，而是满足要求的 数字平方和
平方和，数学术语，定义为
2个或多个数的平方相加。 引自百度百科 举栗子：1^2+2^2+3^2+4^2+...+100^2
平方和 我们没求过，也不知道有啥规律和性质，只好从从前的思考方式去研究一下，看看怎么处理：
先用 数位DP-记忆化搜索 求解问题的方式去思考，如何在求解的过程中 记录/合并信息
既然是 搜索，不妨先用 分治的思想，把 大问题集合 划分成多个 子问题集合，最后再进行 合并
下面我们思考每一位都需要它的后面位给自己 向前返回 些什么信息呢？
假设 我们当前已经搜出了 u-1 层的信息，现在向上 回溯，需要把什么样的信息合并到上面的 大集合 中呢？
从题意要求的结果出发，我们思考一下一个常规形态的位置，怎么样计算出符合条件的 数字平方和：考虑在 搜索 时，如何合并多条搜索分支 回溯 的 平方和信息
假设:
-
目前已经完成了后面
u-1位的填充工作，后u-1位的形式大约是abcd...,为方便起见，设A=abcd..., 回溯到第u位 -
这一位其实可能有
i \in [0,9]种填充办法(有贴上界等原因造成的不可达数位请手动扣除)
现在开始，研究一下带i这一位情况下，所有数字平方和 该如何计算，尝试找出和少一位i的已有结果数据之间的关联关系:
\large \sum_{k}^{}(\overline{iA})^2= \sum_{k}^{}(i \times 10 ^ {u-1}+A)^2 \\
=\sum_{k}^{}\left ( (i \times 10 ^ {u-1})^2 + 2 \times (i \times 10 ^{u-1}) \times A + A^2 \right ) \\
=(\sum_{k}^{}1) (i \times 10^{u-1})^2+ 2 \times (i \times 10 ^ {u-1}) \times \sum_{k}^{}A+\sum_{k}^{}A^2$$
<font color='red' size=4><b>注：$k=$后续符合条件的个数</b></font>
根据上述 **递推式** 可知，我们枚举当前数位填 $i$ 以后下沉 **搜索**，然后 **回溯时** 需要传递的 **信息** 有:
* $\LARGE S_0$:能接在 $i$ 以后的数字 $A$ 的**个数** $\displaystyle \sum_{k}^{}1$
* $\LARGE S_1$:能接在 $i$ 以后的数字 $A$ 的**总和** $\displaystyle \sum_{k}^{}A$
* $\LARGE S_2$:能接在 $i$ 以后的数字 $A$ 的**平方和** $\displaystyle \sum_{k}^{}A^2$
于是把 **搜索结果** 的 **属性值** 开成 **$3$维**，分别记录这三个值： $S_0$(个数), $S_1$(数字总和), $S_2$(数字平方和)
#### 3、并
回溯的时候，调用者收到这三个返回值，对这三个值 **分别** 进行 **合并** 即可
* $\LARGE S_0^{'}$
合并就是直接个数相加即可
```c++
ans.s0 += ret.s0;
```
* $\LARGE S_1^{'}$:
尝试把$sum$展开一下，看看怎么能用后面的已有数据进行描述：
$$\large \sum_{k}^{}(\overline{iA})=\sum_{k}(i \times 10^{u-1}+A)=(\sum_{k}1)\times i \times 10 ^{u-1}+\sum_{k}A$$
至此，就清晰了：
```c++
ans.s1 + = ret.s0 * i * base[u - 1] + ret.s1;
```
* $\LARGE S_2^{'}$:
$$\large \sum_{k}^{}(\overline{iA})^2= \sum_{k}^{}(i \times 10 ^ {u-1}+A)^2 \\
=\sum_{k}^{}\left ( (i \times 10 ^ {u-1})^2 + 2 \times (i \times 10 ^{u-1}) \times A + A^2 \right ) \\
=(\sum_{k}^{}1) (i \times 10^{u-1})^2+ 2 \times (i \times 10 ^ {u-1}) \times \sum_{k}^{}A+\sum_{k}^{}A^2$$
```c++
ans.s2 += i * base[u - 1] * i * base[u - 1] * ret.s0 ;
ans.s2 += 2 * i * base[u - 1] * ret.s1 + ret.s2 ;
```
<font color='red' size=4><b>注意：</b></font>
这题唯一一个 最不起眼的减法操作 在第一步 $calc(r)−calc(l−1)$)，这里也要 **取模**
### 三、预处理$10$的幂次
<font color='red' size=4><b>【不能直接$pow$,因为涉及到取模】</b></font>
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int base[N];
typedef long long ll;
const int mod = 1e9 + 7;
int main() {
base[0] = 1; // 10^0=1,递推的起点
// 1、一日取模，终生取模~
// 2、为了防止运算过程中溢出，所以在乘法时注意加上ll类型转换
// i ∈ [1,N-1] 共19位
for (int i = 1; i < N; i++) base[i] = (ll)10 * base[i - 1] % mod;
for (int i = 1; i < N; i++) printf("%d ", base[i]);
return 0;
}
```
``` c++
输出结果
10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 999999937 999999307 999993007 999930007 999300007 993000007 930000007 300000007 49 490
```
### 四、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
const LL mod = 1e9 + 7;
LL a[N]; // 用于拆分十进制每一位的数组
LL base[N]; // 预处理出的10的幂次方
struct Node {
LL s0; // 满足条件数的个数 Σ(k,1)
LL s1; // 满足条件的数的和 Σ(k,A)
LL s2; // 满足条件的数的平方的和Σ(k,A^2)
} f[N][7][7];
/*
维度1：u: 数位位置
维度2：sum: 前面完成数位的数位和mod 7
维度3：pre: 前面的类前缀和 mod 7
*/
// 枚举位置,每一位加起来的和%7,这个数%7,是不是贴上界
Node dfs(int u, int sum, int pre, bool op) {
// 1、当u==0时,当sum不是7的倍数,并且,pre不是7的倍数时,这个数是合法的,个数记为1返回
// 2、为什么返回的sum==0,pre==0呢？因为这是要返回上一层去算的,这句话还需要仔细体会含义
if (u == 0) return {(sum && pre), 0, 0};
// 记忆化
if (!op && ~f[u][sum][pre].s0) return f[u][sum][pre];
// 上界
int up = op ? a[u] : 9;
// 本状态下u+sum+pre 的统计信息
Node ans = {0, 0, 0};
for (int i = 0; i <= up; i++) {
if (i == 7) continue;
Node ret = dfs(u - 1, (sum + i) % 7, (pre * 10 + i) % 7, op && (i == up));
// 汇集个数
ans.s0 = (ans.s0 + ret.s0) % mod;
// 汇集数字和
ans.s1 = (ans.s1 + ret.s0 * i % mod * base[u - 1] % mod + ret.s1) % mod;
// 汇集数字平方和
ans.s2 = (ans.s2 + i * base[u - 1] % mod * i % mod * base[u - 1] % mod * ret.s0 % mod) % mod;
ans.s2 = (ans.s2 + 2 * i % mod * base[u - 1] % mod * ret.s1 % mod + ret.s2) % mod;
}
// 套路
if (!op) f[u][sum][pre] = ans;
return ans;
}
LL calc(LL x) {
int al = 0;
while (x) a[++al] = x % 10, x /= 10;
return dfs(al, 0, 0, true).s2;
}
int main() {
// 与7无关的数，是数字本身的特性，而且取模是一个固定值，不会因为多输入几次就变化
memset(f, -1, sizeof(f));
// 预处理出10的幂次方【因为涉及到取模，要不这玩意还用预处理？】
base[0] = 1;
for (int i = 1; i < N; i++) base[i] = base[i - 1] * 10 % mod;
int T;
cin >> T;
LL l, r;
while (T--) {
cin >> l >> r;
printf("%lld\n", (calc(r) - calc(l - 1) + mod) % mod); // 操作的每一步都需要注意取模
}
return 0;
}
```
### 五、经验总结
* 涉及到大整数的加法，乘法，需要对大质数取模，看着$int$能装下，还是开类型$ll$吧，运算过程中的溢出也会烦死人~
* 有时，只记录一个属性是无法实现关系的递推的，这时需要采用结构体记录。
* 这个难度的题，(紫题)，目前也就能理解清楚，记忆下来，总结一下。如果出现一个全新的类似题，估计还会挂，蒟蒻和大牛的差距还是巨大的，路还要是一点点走，着急也不是办法，但还好，能看懂。记录一下当前日期$2022-09-14$,也许，两年以后我就是个大牛了~
* 【更新】$2023.6.12$，今天重新复习这道题，对于思路感觉还是挺直接的，要学习数位的一些技巧：比如$\overline{iA}$，$i\times 10^{u-1}+A$之类的常见办法，深刻理解一下$K$的含义，这道题还就是一个简单的扩维、推式子，并不是特别难，看来这东西也是慢慢熟悉的过程，难者不会，会者不难，加油吧！