题目描述
如果一个整数符合下面三个条件之一,那么我们就说这个整数和 7 有关:
整数中某一位是7 ——包含7
整数的每一位加起来的和是 7 的整数倍; ——数位和为7的倍数
这个整数是 7 的整数倍。 ——数字本身是7的倍数
求解:
在一定区间内没有以上性质的数的平方和
难点就在于要求解的是平方和,而不是个数!!!
算法
(记忆化搜索)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=25, M=1e9+7, S=7;
typedef long long LL;
LL t,l,r;
int a[N]; //用于保存分离后的各个数位,0号位置不使用
struct node{
LL cnt; //个数
LL sum; //和
LL psum; //平方和
};
/*
f[pos][dsum][num]表示的状态为:
在不贴合上界,也就是pos位置的取值为0-9,
最高位到pos+1位之间的高位部分, 数字之和(%7)为dsum,整个数字(%7)为num的情况下,
计算出的满足题目性质的数字的属性,结构为node,包括数字个数,和,平方和
如对于数123**,pos=2时,sum=6,num=123,pos从低位开始计数,最低位为1
f数组用于记忆化搜索,存储中间数据,减少递归次数
*/
node f[N][S][S];
LL pow10[N]; //保存10的幂
void init(){
//初始化记忆化搜索数组,无需每次初始化,因为f保存不贴合上界的值,和pos位置的取值无关,所以在多组数据间无需清空
memset(f, -1, sizeof(f)); //-1为全1
//处理10的幂,定义成LL防止越界
pow10[0]=1;
for(int i=1; i<N; i++){
pow10[i]=pow10[i-1]*10%M;
}
return;
}
/*
搜索函数:从a[pos]这个位置开始,之前的数位和为dsum,数字为num的情况下,向下搜索
返回值:返回不超过a[pos]这个数的,小于等于这个数的,并且满足题目要求的那些数的属性
pos:搜索位置
dsum:pos位置之前的数位和
num:pos位置之前的数字
lim:是否贴合上界a[pos],也就是搜索的时候上界的取值范围, lim为假时是从0-9,lim为真时0-a[pos]
*/
node dfs(int pos, LL dsum, LL num, bool lim){
//递归边界,dsum,num模7都不为0,说明满足要求,这里只要个数返回1就可以了,其余值返回0,
//在调用者中,会将上一步的和,平方和累加
if(!pos) return(node){dsum%S&&num%S, 0, 0};
//f数组中已经有值,说明已经计算过,直接返回,注意必须不贴合上界的情况才可以使用f数组
if(!lim && f[pos][dsum][num].cnt>=0) return f[pos][dsum][num];
//没有计算过,开始计算
int up=lim?a[pos]:9; //设定上界
node ans={0,0,0}; //初始化返回值
//枚举pos位置的取值
for(int i=0; i<=up; i++){
if(i==7) continue; //跳过包含7的数
//递归调用下一层函数,注意lim的设置,枚举左边分支时false,右边分支才需要true
node n=dfs(pos-1, (dsum+i)%S, (num*10+i)%S, (lim&&i==up));
//B是加在答案前的高位数字
LL B=i*pow10[pos-1];
//个数直接累加
ans.cnt=(ans.cnt+n.cnt)%M;
//(B+A1)+(B+A2)+...(B+Acnt)=B*cnt+A1+A2+...Acnt=B*cnt+n.sum
ans.sum=(ans.sum+n.cnt*B%M+n.sum)%M;
/*
(B+A1)^2+(B+A2)^2+...+(B+Acnt)^2
=B^2+2BA1+A1^2+B^2+2BA2+A2^2+...+B^2+2BAcnt+Acnt^2
=B^2*cnt+2B(A1+A2+...+Acnt)+(A1^2+A2^2+...Acnt^2)
=B^2*cnt+2Bn.sum+n.psum
*/
ans.psum=(ans.psum+B%M*B%M*n.cnt%M+2*B%M*n.sum%M+n.psum)%M;
}
//不贴合上界时,记忆化,保存结果
if(!lim) f[pos][dsum][num]=ans;
return ans;
}
LL dp(LL x){
int len=0;
while(x){
a[++len]=x%10; //从1开始放置最低位
x/=10;
}
return dfs(len, 0, 0, 1).psum;
}
LL mod(LL x, LL m){
return (x%m+m)%m;
}
int main(){
init();
cin>>t;
while(t--){
cin>>l>>r;
//注意dp(r)有可能小于dp(l-1),所以此处要使用mod函数,对负数取模
cout<<mod(dp(r)-dp(l-1), M)<<endl;
}
}