题目:
单身!
依然单身!
吉哥依然单身!
DS 级码农吉哥依然单身!
所以, 他生平最恨情人节, 不管是 214 还是 77, 他都讨厌!
吉哥观察了 214 和 77 这两个数, 发现:
- 2+1+4=7
- 7+7=7*2
- 77=7*11
最终, 他发现原来这一切归根到底都是因为和 7 有关! 所以, 他现在甚至讨厌一切和 7 有关的数!
什么样的数和 7 有关呢?
如果一个整数符合下面 3 个条件之一, 那么我们就说这个整数和 7 有关 --
1, 整数中某一位是 7;
2, 整数的每一位加起来的和是 7 的整数倍;
3, 这个整数是 7 的整数倍;
现在问题来了: 吉哥想知道在一定区间内和 7 无关的数字的平方和.
Input 输入数据的第一行是 case 数 T(1 <= T <= 50), 然后接下来的 T 行表示 T 个 case; 每个 case 在一行内包含两个正整数 L, R(1 <= L <= R <= 10^18).
Output 请计算 [L,R] 中和 7 无关的数字的平方和, 并将结果对 10^9 + 7 求模后输出. Sample Input
- 3 1 9 10 11 17 17
- Sample Output
- 236 221 0
题解:
1, 不能出现 7 的话可以 dfs 遇到 7 就 continue 掉
2, 每一位加起来不能是 7 的倍数, 那么我们可以 dfs 过程中用一个参数来记录它的取余结果
又因为(a+b)%mod=(a%mod+b%mod)%mod, 所以我们可以是缩减 dp 数组的大小
可能有人会有疑问, 数位上各位相加最大才 9*18. 也就开大一点 dp 数组而已
但是要注意取余 mod 之后不仅仅缩减了 dp 数组的大小, 还缩短了时间, 因为这是在记忆化, 范围越小越能大幅度优化时间复杂度
3, 这个数也不能是 7 的倍数, 那么就可以用秦九韶取余来优化
4, 最难的就是我们最后求的结果是每一个数的平方和, 大家都看到了数据范围是 10^18(我记得有一种方法叫快速相乘, 类似于快速幂, 这里没有试这一种方法)
在网上找了一篇博客: http://www.freesion.com/article/9575132166/
代码:
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #include<iostream>
- using namespace std;
- const int maxn=105;
- const int mod = 1e9+7;
- typedef long long ll;
- struct DP
- {
- ll cnt, sum, sqsum;
- DP () {}
- DP (ll cnt, ll sum, ll sqsum): cnt(cnt), sum(sum), sqsum(sqsum) {}
- }dp[20][10][10];
- //dp[x][y][z]表示在数字的第 x 位上, 且各位数字之和取余 7 得结果(不取余直接存的话会内存
来源: http://www.bubuko.com/infodetail-3300587.html