\(Description:\)
给出区间 \([L,R]\) 求出区间中所有满足没有 \(7\) 这个数并且这个数不会被 \(7\) 整除，同时这个数各位上的和不能被 \(7\) 整除。求 \([L,R]\) 的区间中满足这些条件的数的平方和。
\(Sample\) \(Input:\)
3
1 9
10 11
17 17
\(Sample\) \(Output:\)
236
221
0
\(Solution:\)
这题老好玩了，坑了我一个早上，发现他要咱们求得是平方和。
好像不可做的样子，看了看题解，其实也没有想象的那么难写。
但是我们要把一些别的推导出平方和的东西记录下来。
考虑已经求出了后面的几位数的数字，是 \(f_i\)
那么当前这个数是 \(x\)
那么平方和为
\(\sum_{i=1}^{n}(x+f_i)^2=\sum_{i=1}^{n}(x^2+2*f_i*x+(f_i)^2)\)
拆除 \(sigma\)
\(\sum=n*x^2+2*x*\sum_{i=1}^{n}f_i+\sum(f_i)^2\)
那么我们只要记录
当前后几位组成的数有几个 ：\(cnt\) ，
后面几个数的和 \(sum\) ，
上一次的平方和 \(sqr\)，
那么就可以转移了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T;
const int N=25,M=10,p=1e9+7;
int a[N];
int digit[N];
struct node{
int cnt;
int sum;
int sqr;
bool exist;
inline void clear() {
cnt=sum=sqr=0;
exist=false;
}
}c,b,f[N][M][M];
inline node dfs(int len,int res,int sum,bool limit){
if(len<=0) {
node tmp;tmp.clear();
if(res && sum){
tmp.cnt=1;
return tmp;
}
return tmp;
}
if(!limit && f[len][res][sum].exist) return f[len][res][sum];
node ret;ret.clear();
int up_bound=(limit)?digit[len]:9;
for(int i=0;i<=up_bound;++i){
if(i==7) continue;
node x; x.clear();
int tmp=(a[len-1]*i)%p;
x=dfs(len-1,(res+i)%7,(sum*10+i)%7,limit && (i==up_bound));
ret.cnt+=x.cnt;
ret.cnt%=p;
ret.sum+=(x.sum+(tmp*x.cnt)%p)%p;
ret.sum%=p;
ret.sqr+=((x.cnt*tmp)%p*tmp)%p;
ret.sqr%=p;
ret.sqr+=((2*tmp)%p*x.sum)%p;
ret.sqr%=p;
ret.sqr+=x.sqr;
ret.sqr%=p;
}
if(!limit) f[len][res][sum]=ret,f[len][res][sum].exist=true;
return ret;
}
inline node solve(int x){
int cnt=0;
memset(f,0,sizeof(f));
while(x){
digit[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,0,true);
}
signed main(){
a[0]=1;
for(int i=1;i<=20;++i) a[i]=(a[i-1]*10)%p;
scanf("%lld",&T);
while(T--){
int l=0,r=0;
scanf("%lld%lld",&l,&r);
c=solve(r);
b=solve(l-1);
printf("%lld\n",((c.sqr-b.sqr)%p+p)%p);
}
return 0;
}