|
|
|
|
|
## [$AcWing$ $1086$. 恨$7$不成妻](https://www.acwing.com/problem/content/1088/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
单身！
|
|
|
|
|
|
|
|
|
|
|
|
依然单身！
|
|
|
|
|
|
|
|
|
|
|
|
吉哥依然单身！
|
|
|
|
|
|
|
|
|
|
|
|
$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}$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
3
|
|
|
|
|
|
1 9
|
|
|
|
|
|
10 11
|
|
|
|
|
|
17 17
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
236
|
|
|
|
|
|
221
|
|
|
|
|
|
0
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、题目解析
|
|
|
|
|
|
|
|
|
|
|
|
#### 1、递【传递信息】
|
|
|
|
|
|
这题如果只是求整数区间 $[l,r]$ 内满足要求的数的 **个数**，难度可以归为 **简单**
|
|
|
|
|
|
|
|
|
|
|
|
我们先想一下如何求解我说的这个 **简单问题**
|
|
|
|
|
|
|
|
|
|
|
|
毫无疑问是用 **数位$DP$** 来求解，那么在从前向后的搜索过程中，需要 <font color='red' size=4><b>向后传递</b></font> 的参数有：
|
|
|
|
|
|
|
|
|
|
|
|
* 前 $u$ 位数位上的数字之和模 $7$ 的余数 <font color='red'>$sum$</font>(对应题目中的②)
|
|
|
|
|
|
|
|
|
|
|
|
* 前 $u$ 位模 $7$ 的余数 <font color='red'>$pre$</font>(对应题目中的③)
|
|
|
|
|
|
|
|
|
|
|
|
>① 某个数位是不是$7$，直接判断即可，不用传递。
|
|
|
|
|
|
|
|
|
|
|
|
只有前一个位置 **传递** 这两个信息，下一个数位才好判断自己怎么办，也就比 **前$5$道数位$DP$** 多了一个参数,**表现在记忆化中就是数组多了一维罢了**。
|
|
|
|
|
|
|
|
|
|
|
|
#### 2、归【合并信息】
|
|
|
|
|
|
|
|
|
|
|
|
可惜本题要求的不是满足要求的 **数字的个数**，而是满足要求的 **<font color='red' size='4px'>数字平方和</font>**
|
|
|
|
|
|
|
|
|
|
|
|
> 平方和，数学术语，定义为$2$个或多个数的平方相加。 引自百度百科
|
|
|
|
|
|
> 举栗子：$1^2+2^2+3^2+4^2+...+100^2$
|
|
|
|
|
|
|
|
|
|
|
|
**平方和** 我们没求过，也不知道有啥规律和性质，只好从从前的思考方式去研究一下，看看怎么处理：
|
|
|
|
|
|
|
|
|
|
|
|
先用 **数位$DP$-记忆化搜索** 求解问题的方式去思考，如何在求解的过程中 **<font color='blue'>记录/合并信息</font>**
|
|
|
|
|
|
|
|
|
|
|
|
既然是 **搜索**，不妨先用 **分治的思想**，把 **大问题集合** 划分成多个 **子问题集合**，最后再进行 **合并**
|
|
|
|
|
|
|
|
|
|
|
|
下面我们思考每一位都需要它的后面位给自己 <font color="red" size='4px'> <b>向前返回</b></font> 些什么信息呢？
|
|
|
|
|
|
|
|
|
|
|
|
**假设** 我们当前已经搜出了 $u-1$ 层的信息，现在向上 **回溯**，需要把什么样的信息合并到上面的 **大集合** 中呢？
|
|
|
|
|
|
|
|
|
|
|
|
从题意要求的结果出发，我们思考一下一个常规形态的位置，怎么样计算出符合条件的 **数字平方和**：考虑在 **搜索** 时，如何合并多条搜索分支 **回溯** 的 **平方和信息**
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<font color='red' size=4><b>假设:</b></font>
|
|
|
|
|
|
* 目前已经完成了后面$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$的含义，这道题还就是一个简单的扩维、推式子，并不是特别难，看来这东西也是慢慢熟悉的过程，难者不会，会者不难，加油吧！
|
