不会数位$DP$的这里指路一篇介绍非常详细的数位$DP$的$blog$:点这里。
以上只是简单分析，我们还并没有真正的进行状态转移和计算，那么根据题意，首先是需要知道整数的每一位加起来的和是$7$的整数倍以及该整数是$7$的整数倍，这个好处理，在我们的前面的题中有类似的题型，这已经在我们的$f$数组的第三维和第四维了。所以难点就在于怎么处理整数的平方和。我们看下面的公式推导：
我们用$jA$来表示$i$位数，而其中的$A$为$i-1$位数。设这个状态有$t$个符合要求的数，分别是$A_1$~$A_t$。 那么，平方和易得为：
$(jA_1)^2+(jA_2)^2+(jA_3)^2+…+(jA_{t-1})^2+(jA_t)^2$
（我们分割表示将$A$提取出来。）
$=(j10^{i-1}+A_1)^2+(j10^{i-1}+A_2)^2+(j10^{i-1}+A_3)^2+…+(j10^{i-1}+A_{t-1})^2+(j*10^{i-1}+A_t)^2$
（平方和公式）
$=t*(j10^{i-1})^2+2(j10^{i-1})(A_1+…+A_t)+(A_1^2+…+A^2)$
这样，在这个式子中，由于$j$已知，所以我们发现$f$数组需要保存三个值。$A$的$0$次方之和，也就是符合要求的数，$A$的$1$次方之和，也就是符合要求的除去$j$的$i-1$位数相加，$A$的$2$次方之和，也就是符合要求的除去$j$的$i-1$位数平方相加。我们分别用$s_0,s_1,s_2$
分别代表上述的三个值。
那么这里我们需要怎么求$s_1$，如下：
注：这里的$s_1$为$i+1$位的$s_1$，而它存储的就是$i$位的$A$。
$jA_1+…+jA_t$
$=j*10^{i-1}+(A_1+…+A_t)$
所以我们的$f$应该是一个结构体数组，它需要存取$s_0,s_1,s_2$。那么预处理根据上述分析其实就简单了。那么就按照数位$DP$的套路解决这道题即可。需要注意这道题好多坑点，多取模，足够细心才可以解决。（调$Bug$调了好久。快绝望了。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| /**
*@filename:恨7不成妻
*@author: pursuit
*@csdn:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-05-12 21:19
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
const ll P = 1e9+7;
//需要满足三个性质。
//1.不含7.
//2.各位数字之和模7不为0.an-1+...+a0%7!=0.
//3.该数模7不为0.an-1*pow(10,n-1)+...+a0+pow(10,0)%7!=0
struct F{
ll s0,s1,s2;//s0为符合要求的数。s1为符合要求的数1次方之和，s2为符合要求的数的2次方之和。
}f[N][10][7][7];//f[i][j][k][u]表示总共有i位数且最高位是j，该数值模7为k，各位数数字之和模7为u的所有数的s0,s1,s2.
//进行初始化。
int t;//测试数。
ll l,r;
ll power7[N],power9[N];//power7[i]存储10^i余7的余数，power9[i]存储10^i余P的余数。
ll mod(ll x,ll y){
return (x%y+y)%y;
}
void init(){
//确定初始值，位数为1的情况。
for(int j=0;j<10;j++){
if(j==7)continue;
//根据性质排除不符合要求的。
F &v=f[1][j][j%7][j%7];//这里用引用减少代码量。
v.s0++;
v.s1+=j;
v.s2+=j*j;
}
ll power = 10;//辅助作用，表示10的i-1次方。
for(int i=2;i<N;i++,power*=10){
for(int j=0;j<10;j++){
if(j==7)continue;//排除不符合要求的数。
for(int k=0;k<7;k++){
for(int u=0;u<7;u++){
for(int q=0;q<10;q++){
//枚举i-1的最高位。
if(q==7)continue;
F &x=f[i][j][k][u],y=f[i-1][q][mod(k-j*(power%7),7)][mod(u-j,7)];
//s0,s1,s2都是通过公式就算得到。
x.s0=mod(x.s0+y.s0,P);
x.s1=mod(x.s1+1LL*j%P*(power%P)%P*y.s0%P+y.s1,P);
x.s2=mod(x.s2+
1LL*j%P*y.s0%P*(power%P)%P*j%P*(power%P)%P+
1LL*y.s1%P*2%P*j%P*(power%P)%P+y.s2,P);
}
}
}
}
}
//这里处理为了方便以及降低时间复杂度。
power7[0]=1,power9[0]=1;
for(int i=1;i<N;i++){
power7[i]=power7[i-1]*10%7;
power9[i]=power9[i-1]*10%P;
}
}
F get(int i,int j,int k,int u){
//因为f[i][j][k][u]是本身模7等于k，且各位数之和模7等于u的，所以我们需要找出符合条件的集合。
ll s0=0,s1=0,s2=0;
for(int x=0;x<7;x++){
for(int y=0;y<7;y++){
if(x==k||y==u)continue;
F v=f[i][j][x][y];
s0=mod(s0+v.s0,P);
s1=mod(s1+v.s1,P);
s2=mod(s2+v.s2,P);
}
}
return {s0,s1,s2};
}
ll dp(ll n){
if(!n)return 0;//0的平方和为0.
vector<int> a;
ll temp=n%P;//备份一个n，供后面判断n使用。
while(n)a.push_back(n%10),n/=10;
ll last_a=0,last_b=0;//这里我们需要存储前缀的本身值和前缀的个位数之和。
ll ans=0;//答案。
for(int i=a.size()-1;i>=0;i--){
int x=a[i];
for(int j=0;j<x;j++){
//走左分支。
if(j==7)continue;
//我们需要将符合条件的数筛出来，这里要用到一个get函数。
//求得本身模7不等于a，并且各位数之和模7不等b的集合，此时就可以使用预处理出来的结构体
int k=mod(-last_a*power7[i+1],7),u=mod(-last_b,7);
F v=get(i+1,j,k,u);
//cout<<v.s0<<" "<<v.s1<<" "<<v.s2<<endl;
//根据公式求解s2.
//j就是last_a.
ans=mod(ans+
1LL*(last_a%P)*(last_a%P)%P*(power9[i+1]%P)%P*(power9[i+1]%P)%P*v.s0%P+
1LL*2*last_a%P*(power9[i+1]%P)%P*v.s1%P+
v.s2,P);
//cout<<ans<<endl;
}
//判断x。
if(x==7)break;
//走右分支更新。
last_a=last_a*10+x;
last_b+=x;
//判断自己本身是否符合要求。
if(!i&&last_a%7&&last_b%7){
ans=mod(ans+temp*temp%P,P);
}
}
return ans;
}
int main(){
init();
cin>>t;
while(t--){
cin>>l>>r;
cout<<mod(dp(r)-dp(l-1),P)<<endl;
}
return 0;
}
/*
1
1 1000000000000000000
*/
|
HeZephyr
支付宝
微信