题目描述
原题来自：HDU 4507
#10168. 「一本通 5.3 练习 3」恨 7 不成妻 - 题目 - LibreOJ (loj.ac)
单身！
依然单身！
吉哥依然单身！
DS 级码农吉哥依然单身！
所以，他平生最恨情人节，不管是 还是 ，他都讨厌！
吉哥观察了 和 这两个数，发现：
2+1+4&=7\\ 7+7&=7\times 2\\ 77&=7\times 11 \end{align}$$ 最终，他发现原来这一切归根到底都是因为和 $7$ 有关！所以，他现在甚至讨厌一切和 $7$ 有关的数！ 什么样的数和 $7$ 有关呢？如果一个整数符合下面三个条件之一，那么我们就说这个整数和 $7$ 有关： 1. 整数中某一位是 $7$； 2. 整数的每一位加起来的和是 $7$ 的整数倍； 3. 这个整数是 $7$ 的整数倍。 现在问题来了：吉哥想知道在一定区间内和 $7$ 无关的数字的平方和。 ### 输入格式 输入数据的第一行是测试数据组数 $T$，然后接下来的 $T$ 行表示 $T$ 组测试数据。 每组数据在一行内包含两个正整数 $L, R$。 ### 输出格式 对于每组数据，请计算 $[L,R]$ 中和 $7$ 无关的数字的平方和，并将结果对 $10^9+7$ 取模后输出。 ### 样例 输入 ```c 3 1 9 10 11 17 17 ``` 输出 ```c 236 221 0 ``` ### 数据范围与提示 对于全部数据，$1\le T\le 50,1\le L\le R\le 10^{18}$。 ## 思路 题意概括一下就是, 找出区间$[L,R]$内, 所有与$7$无关的数字的平方和。 先分为两步, 找出与$7$无关的数字, 求他们的平方和。 与$7$有关的条件为： 1. 整数中某一位是 $7$； 2. 整数的每一位加起来的和是 $7$ 的整数倍； 3. 这个整数是 $7$ 的整数倍。 这里显然就需要数位DP来做了。 依然是设$dp(n)$函数求$[0,n]$中所有与$7$无关的数字的平方和, 先进行树型分解：![[07 - ARCHIVES/知识库/计算机/软件工程/操作系统/CSAPP/第1章 计算机系统漫游/图片/Pasted image 20221229210115.png]] 答案是左分支加上右分支（n）的值, 先考虑预处理左分支。 即当前状态为 `An-1 x ... ... ... ... ` 时, 的平方和结果。为了满足不与$7$有关的条件, 需要记录当前最高位的值 `j`, 各位数字和 `a`, 连起来的整数 `b`。这里只需要判断是否为7的倍数, 故 `a` 和 `b` 取 7 的余数即可。 状态表示：`f[i][j][a][b]` 长度为i, 最高位为j, 各位数字和取模7的值a, 连起来的整数对7取模的值b。 状态计算：![[07 - ARCHIVES/知识库/计算机/软件工程/操作系统/CSAPP/第1章 计算机系统漫游/图片/Pasted image 20221229231937.png]] 而在dp求解时, 当前位确定后, 也需要计算出展开后式子的平方和, 再累加到结果上。 ## 代码 ```c++ const int N = 20, P = 1e9 + 7; typedef long long LL; struct F { int s0, s1, s2; } f[N][10][7][7]; int power7[N], power9[N]; LL mod(LL x, int y) { return (x % y + y) % y; } void init() { for (int i = 0; i <= 9; i++) if (i != 7) { auto &v = f[1][i][i % 7][i % 7]; v.s0++; v.s1 += i; v.s2 += i * i; } LL power = 10; for (int i = 2; i < N; i++, power *= 10) 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++) { if (k == 7) continue; auto &v1 = f[i][j][a][b], &v2 = f[i - 1][k][mod(a - j * (power % 7), 7)][mod(b - j, 7)]; v1.s0 = (v1.s0 + v2.s0) % P; v1.s1 = (v1.s1 + j * (power % P) * v2.s0 + v2.s1) % P; v1.s2 = (v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0 % P + 2 * j * (power % P) % P * v2.s1 % P + v2.s2) % P; } } power7[0] = power9[0] = 1; for (int i = 1; i < N; i++) { power7[i] = power7[i - 1] * 10 % 7; power9[i] = power9[i - 1] * 10ll % P; } } 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; auto &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}; } LL dp(LL n) { if (!n) return 0; LL backup_n = n % P; vector<int> nums; while (n) nums.push_back(n % 10), n /= 10; LL res = 0; LL last_a = 0, last_b = 0; // a是整个数, b是各个数字和 for (int i = nums.size() - 1; i >= 0; i--) { int x = nums[i]; for (int j = 0; j < x; j++) { if (j == 7) continue; // 对于该状态 last_a j ... ... ... int a = mod(-last_a % 7 * power7[i + 1], 7); // 即 (j...) + last_a mod 7 != 0, (j...) = -last_a % 7 int b = mod(-last_b, 7); auto v = get(i + 1, j, a, b); // 要求是不满足 %7=0, 故其他的a,b取值都可以 res = (res + ((last_a % P) * (last_a % P) % P * power9[i + 1] % P * power9[i + 1] % P * v.s0 % P + 2 * (last_a % P) * power9[i + 1] % P * v.s1 % P + v.s2) % P) % P; } if (x == 7) break; last_a = last_a * 10 + x; last_b = last_b + x; if (!i && last_a % 7 != 0 && last_b % 7 != 0) res = (res + backup_n * backup_n) % P; } return res; } 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; } ```