题目描述：
单身！
依然单身！
吉哥依然单身！
DS 级码农吉哥依然单身！
所以，他平生最恨情人节，不管是 214 还是 77，他都讨厌！
吉哥观察了 214 和 77 这两个数，发现：
2+1+4=7
7+7=7×2
77=7×11
最终，他发现原来这一切归根到底都是因为和 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分析：
本题是比较难的数位DP问题，思路并不复杂，只是代码较为繁琐，因为数字是long long类型才能存的下的，所以在计算一连串乘法时需要不停的取模，比如long long a,b; 计算a * b就应该写成(a % P) * (b % P) % P，其中P = 1e9 + 7，另外对于int类型的数组，如果计算的中间结果超过了int，需要及时的强转为long long，忽视其中任何一步可能爆int的乘法运算，都会引起结果的错误。下面正式分析本题的解法。
直接dfs的话思路比较简洁，但是不方便进行记忆化搜索，需要存储的东西太多了，而不进行记忆化搜索显然会超时，所以还是采用动态规划的解法。一般数位DP的题目用f[i][j]表示开头是j的i位数的满足条件的数字的个数，比如不含7的i位数的个数就很容易用f[i][j]表示出来，但是题目新增了两个条件，这个数不能被7整除，这个数的每一位之和不能被7整除，所以对整数的划分应该划分为这个数模上7的余数以及数的各位之和模上7的余数这两个等价类，因此要对f数组增加两维。f[i][j][a][b]表示一个i为数最高位是j，各位之和模上7等于a，这个数模上7等于b，注意这里还没有给出f数组的含义，因为如果只是统计这样数的个数，那么本题就相当简单了，但是题目要求的是与7无关整数的平方和，这就相当复杂了，如果我们算到最后一位才去加上这个数的平方和，超时是肯定的，我们需要求的是i位数中以j开头的满足条件的整数的平方和是多少，需要有明确的递推式。下面开始推公式：
设满足条件的以j开头的i位数有jx1，jx2，...，jxn。其中xi表示j后面的i-1位数，我们要求这些数的平方和S，也就是S = （jx1）^2 + ... + (jxn)^2。又jxi = j * 10^(i-1) + xi，故S = (j*10^(i-1))^2 + 2 * j * 10^(i-1) * x1+ x1^2) + ... + (j*10^(i-1))^2 + 2 * j * 10^(i-1) * xn + xn^2) = n * j*10^(i-1))^2 + 2 * j * 10^(i-1) * (x1+...+xn) + (x1^2 +...+ xn^2)，观察表达式中出现的项，分别是满足条件数的个数n，这些数中后n-1位组成数字的和x1 + ... + xn，以及这些数后n-1位组成数字的平方和。所以f数组要存储的是以j开头满足条件的i位数的个数、和以及平方和，可以使用结构体存储，s0表示个数，s1表示和，s2表示平方和。下面要考虑的是，如何通过f[i-1][k][c][d]的s0,s1,s2推出f[i][j][a][b]的这些信息，首先考虑c和d的取值，i位数的各位之和是a，则前i-1位的和是a - j，故c = a - j，当然还要对7取模。又前i-1位数j * 10^(i-1) + d对7取模结果是b，所以d = b - j * 10^(i-1)再对7取模。令v1 = f[i][j][a][b]，v2 = f[i-1][k][c][d]。显然v1.s0 += v2.s0。那么如何通过前i-1位数组成数字的和求出加上最高位j组成数字的和呢？jx1 + jx2 + ...+jxn = (j*10^(i-1) + x1)+...+(j*10^(i-1)+xn) = n * j * 10^(i-1) + (x1 + ... + xn)即v1.s1 += v2.s0 * j * 10^(i-1) + v2.s1，最后根据本段开头推出的公式得v1.s2 += v2.s0 * j*10^(i-1))^2 + 2 * j * 10^(i-1) * v2.s1 + v2.s2，当然代码在实行这部分时每步乘法的后面都需要加上取模运算，表达式会更加复杂。
现在我们知道了以j开头的i位数的与7无关的数的平方和是怎么有前面的j和后面的x推出来了，问题就解决了一大半，剩下的就是自高向低逐位枚举n的每一位了，需要存储以及枚举的位数的数字之和last1，以及已经枚举的数组成的数字last2。我们要求f[n][j][a][b]，其中a与b都不能是0，我们不妨先求出能够使a和b是0的数是哪些，然后排除这些数即可。要想前面的数字last1与后面的数字组合起来的数与7无关，则需要求出f[i+1][j][c][d]中的c和d是多少时，(c + last1) % 7 == 0，即c = mod(-last1,7)，并且(last2 * 10^(i+1) + d) % 7 == 0，d = mod(-last2 * 10^(i+1),7)，（这里为什么是乘以10的i+1字方？是因为枚举第i位时last2存储的还是i+1前面的数）。我们知道了c和d取这些值时会使得最终的数与7有关，那么我们枚举所有的c和d不为该值时的数，将题目的平方和加起来就是我们需要求的结果了。
PS：可能即使看上面那么详细的推导过程还是一头雾水，看不懂的地方看代码时回过头来看分析过程就可以看懂了。本题就是一个取模麻烦，公式推导出来实现还是很简单的。
#include
#include
#include
using namespace std;
const int N = 20,P = 1e9 + 7;
typedef long long ll;
int p7[N],p9[N];
struct F{
int s0,s1,s2;
}f[N][10][7][7];
int mod(ll x,int y){//取模函数，主要针对x是负数
return (x % y + y) % y;
}
void init(){
for(int i = 0;
i < 10;
i++){
if(i == 7)continue;
auto &v = f[1][i][i%7][i%7];
v.s0++,v.s1 += i,v.s2 += i * i;
}
ll p = 10;
for(int i = 2;
i < N;
i++,p *= 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,7)][mod(b - p * j,7)];
v1.s0 = mod(v1.s0 + v2.s0,P);
v1.s1 = mod(v1.s1 + v2.s1 + j * (p % P) % P * v2.s0,P);
v1.s2 = mod(v1.s2 + j * j * (p % P) % P * (p % P) % P * v2.s0 + 2 * j * p % P * v2.s1 + v2.s2,P);
}
}
}
}
}
p7[0] = p9[0] = 1;
//预处理10的若干字方对7和P取模的结果，打表备查
for(int i = 1;
i < N;
i++){
p7[i] = (p7[i - 1] * 10) % 7;
p9[i] = (ll)p9[i - 1] * 10 % P;
//这里如果不强转为ll中间结果会爆int
}
}
F getf(int x,int y,int a,int b){//找出第三维第四维不是a和b的数的个数、和以及平方和
int s0 = 0,s1 = 0,s2 = 0;
for(int i = 0;
i < 7;
i++){
if(i == a)continue;
for(int j = 0;
j < 7;
j++){
if(j == b)continue;
auto &v = f[x][y][i][j];
s0 = (s0 + v.s0) % P;
s1 = (s1 + v.s1) % P;
s2 = (s2 + v.s2) % P;
}
}
return {s0,s1,s2};
}
int get(ll n){
if(!n)return 0;
ll m = n;
vector num;
while(n)num.push_back(n % 10),n /= 10;
int res = 0;
ll last1 = 0,last2 = 0;
for(int i = num.size() - 1;
i >= 0;
i--){
int x = num[i];
for(int j = 0;
j < x;
j++){
if(j == 7)continue;
int a = mod(-last1,7),b = mod(-last2 * p7[i + 1],7);
auto v = getf(i + 1,j,a,b);
res = mod(res + last2 % P * (last2 % P) % P * p9[i + 1] % P * p9[i + 1] % P * v.s0 % P
+ 2 * last2% P * p9[i + 1] % P * v.s1 % P + v.s2,P);
}
if(x == 7)break;
last1 += x,last2 = last2 * 10 + x;
if(!i && last1 % 7 && m % 7)res = (res + m % P * (m % P)) % P;
}
return res;
}
int main(){
int T;
ll L,R;
cin>>T;
init();
while(T--){
cin>>L>>R;
cout< 【算法提高课|AcWing 1086 恨7不成妻】
推荐阅读
- 算法与数据结构|算法与数据结构——AcWing算法题常用代码模板
- ACM专题学习|小沙的算数--并查集 (联通块)
- 动态规划|符环 解题笔记
- leetcode刷题记录|反转字符串——LC344题
- #|蓝桥杯31天冲刺打卡题解（Day6）
- LeetCode|LeetCode 467. 环绕字符串中唯一的子字符串 -- 动态规划
- LeetCode编程题解法汇总|力扣解法汇总2044-正则表达式匹配
- 剑指offer|统计回文oj
- 数学随想|生态学经典（捕食者和被捕食者模型）