这道题真的巨难,大家都要注意脱发,如果想做这道题,那么基本上那天就别干什么其他的费脑子的事了,不然脑子会不够用……不过这只是我(蒟蒻)的个人建议,所以大神们应该不用采纳也能轻易解出此题,大家都不要喷我呀~。
还有,如果有对我的代码有建议的一定要大胆提出,我会改正滴
QAQ
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int P=1e9+7;
struct ST{
int s0,s1,s2;
}f[20][10][7][7];
int pp7[20],pp9[20];
int mod(long long x,int y){return (x%y+y)%y;}
ST get(int i,int j,int a,int b)
{
int s0=0,s1=0,s2=0,x,y;
for(x=0;x<7;x++)for(y=0;y<7;y++)if(x!=a&&y!=b){
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};
}
int DP(long long n)
{
if(!n)return 0;
long long bun=n%P,eea=0,eeb=0;
vector<int>num;
while(n)num.push_back(n % 10),n/=10;
int ans=0,i,x,j,a,b;
for(i=num.size()-1;i>=0;i--){
x=num[i];
for(j=0;j<x;j++){
if(j==7)continue;
a=mod(-eea*pp7[i+1],7),b=mod(-eeb,7);
auto v=get(i+1,j,a,b);
ans=mod(ans+(eea%P)*(eea%P)%P*pp9[i+1]%P*pp9[i+1]%P*v.s0%P+v.s2+2*eea%P*pp9[i+1]%P*v.s1,P);
}
if(x==7)break;
eea=eea*10+x,eeb+=x;
if(!i&&eea%7&&eeb%7)ans=(ans+bun*bun)%P;
}
return ans;
}
int main()
{
int T,i,j,a,b,k;
long long power=10,l,r;
scanf("%d",&T);
for(i=0;i<=9;i++){
if(i==7)continue;
auto& v=f[1][i][i%7][i%7];
v.s0++,v.s1+=i,v.s2+=i*i;
}
for(i=2;i<20;i++,power*=10)for(j=0;j<=9;j++){
if(j==7)continue;
for(a=0;a<7;a++)for(b=0;b<7;b++)for(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)][mod(b-j,7)];
v1.s0=mod(v1.s0+v2.s0,P);
v1.s1=mod(v1.s1+v2.s1+j*(power%P)%P*v2.s0,P);
v1.s2=mod(v1.s2+j*j*(power%P)%P*(power%P)%P*v2.s0+v2.s2+2*j*power%P*v2.s1,P);
}
}
pp7[0]=1,pp9[0]=1;
for(i=1;i<20;i++)pp7[i]=pp7[i-1]*10%7,pp9[i]=pp9[i-1]*10ll%P;
while(T--){
scanf("%lld%lld",&l,&r);
printf("%lld\n",mod(DP(r)-DP(l-1),P));
}
return 0;
}
大家都要加油鸭🦆