恨7不成妻 题解
分析
数位 \(DP\)
考虑题目中的两个条件，每一位不等于 \(7\) 直接枚举时把 \(7\) 排除，其他两种情况直接放在状态里。
因为题目要求平方和，我们考虑每次加上一位(设加入的是第 \(i\) 位)时会发生什么
设原平方和为
\[\sum_{k=1}^t a_k^2 \]加入一位 \(p\) 之后每个数变成 \(a_k+p\times 10^{i-1}\)
现平方和为
\[\begin{matrix} \\&\sum_{k=1}^t (a_k+p\times 10^{i-1})^2 \\=&\sum_{k=1}^t [(p\times 10^{i-1})^2+2a_kp\times 10^{i-1}+a_k^2] \\=&t(p\times 10^{i-1})^2+2p\times 10^{i-1}\sum_{k=1}^ta_k+\sum_{k=1}^ta_k^2 \end{matrix} \]可以看出一共需要维护三个东西：个数，和，平方和。
设状态 \(f[i,j,k],g[i,j,k],h[i,j,k]\) 为一共有 \(i\) 位，各位和对 \(7\) 取模为 \(j\)，这个数对 \(7\) 取模为 \(k\) 的个数，和，平方和。
状态转移方程也很好列出
设 \(b=(j-p)\bmod 7,c=(l-p\times 10^{i-1})\bmod 7,x=p\times10^{i-1}\)
\[f[i,j,k]=\sum_{p=0}^9 f[i-1,b,c]\times[p\ne7] \]\[g[i,j,k]=\sum_{p=0}^9 (f[i-1,b,c]\times x+g[i-1,b,c])\times[p\ne7] \]\[h[i,j,k]=\sum_{p=0}^9 (f[i-1,b,c]\times x\times x+g[i-1,b,c]\times x+h[i-1,b,c])\times[p\ne7] \]然后考虑每一位怎么求
题目要求 \(l\sim r\)，我们就可以用 \((0,r+1)\) 的答案减去 \((0,l)\) 的答案（闭区间的原因是不用考虑边界条件），所以先考虑 \((0,r+1)\)。
数位 \(DP\) 套路，先拆位。
然后对于每一位，从高到底枚举填哪个数，对于不是最大值的，直接暴力填累加答案，对于是最大值的直接跳过看下一位。注意枚举每一位的时候不要枚举到 \(7\)。
我们另设三个变量，方便记录之前填的数字。
\(now\) 前面的数字对 \(7\) 取模，\(sum\) 前面的每一位之和对 \(7\) 取模，\(tmp\) 前面的每一位（可先对 \(10^9+7\) 取模。
对于 \(p<a_i\) 的时候。
设 \(b=(7-(sum+p))\bmod 7,c=(7-(now+p\times 10^{i-1}))\bmod 7,x=tmp+p\times10^{i-1}\)
\[ans=ans+\sum_{j=0}^7\sum_{l=0}^7[j\ne b][l\ne c](f[i-1,j,l]\times x\times x+2g[i-1,j,l]\times x+h[i-1,j,l]) \]注意到第 \(i\) 位的时候如果 \(a_i=7\) 需要直接退出。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
char ch=getchar();int x=0;bool f=1;
while(ch<'0'||'9'<ch){if(ch=='-')f=0;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int mod=1e9+7;
int f[20][7][7],g[20][7][7],h[20][7][7],num[20],ksm[20];
void init(){
ksm[0]=num[0]=1;for(int i=1;i<=19;i++)num[i]=num[i-1]*10%7,ksm[i]=ksm[i-1]*10%mod;
f[0][0][0]=1;
for(int i=1;i<=19;i++)
for(int j=0;j<7;j++)
for(int l=0;l<7;l++){
for(int p=0;p<10;p++)if(p!=7){
int a=i-1,b=((j-p)%7+7)%7,c=((l-p*num[i-1])%7+7)%7,x=p*ksm[i-1]%mod;
(f[i][j][l]+=f[a][b][c])%=mod;
(g[i][j][l]+=f[a][b][c]*x%mod+g[a][b][c])%=mod;
(h[i][j][l]+=(f[a][b][c]*x%mod*x%mod+g[a][b][c]*x%mod*2%mod+h[a][b][c])%mod)%=mod;
}
}
return;
}
int len,a[20];
inline int solve(int r){
len=0;while(r)a[++len]=r%10,r/=10;
int ans=0,now=0,sum=0,tmp=0;
for(int i=len;i;i--){
for(int p=0;p<a[i];p++)if(p!=7){
int a=i-1,b=(7-(sum+p)%7)%7,c=(7-(now+p*num[i-1])%7)%7,x=(tmp+p*ksm[i-1]%mod)%mod;
for(int j=0;j<7;j++)
if(j!=b)
for(int l=0;l<7;l++)
if(l!=c)
(ans+=(f[a][j][l]*x%mod*x%mod+g[a][j][l]*x%mod*2%mod+h[a][j][l])%mod)%=mod;
}
if(a[i]==7)break;
(tmp+=a[i]*ksm[i-1]%mod)%=mod;
(now+=a[i]*num[i-1]%7)%=7;
(sum+=a[i])%=7;
}
return ans;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
init();
int T=read();
while(T--){
int l=read(),r=read();
printf("%lld\n",(mod+solve(r+1)-solve(l))%mod);
}
return 0;
}