吉哥系列故事——恨7不成妻
Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
单身!
依然单身！
吉哥依然单身！
DS级码农吉哥依然单身！
所以，他生平最恨情人节，不管是214还是77，他都讨厌！
吉哥观察了214和77这两个数，发现：
2+1+4=7
7+7=7*2
77=7*11
最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！
什么样的数和7有关呢？
如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
1、整数中某一位是7；
2、整数的每一位加起来的和是7的整数倍；
3、这个整数是7的整数倍；
现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
依然单身！
吉哥依然单身！
DS级码农吉哥依然单身！
所以，他生平最恨情人节，不管是214还是77，他都讨厌！
吉哥观察了214和77这两个数，发现：
2+1+4=7
7+7=7*2
77=7*11
最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！
什么样的数和7有关呢？
如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
1、整数中某一位是7；
2、整数的每一位加起来的和是7的整数倍；
3、这个整数是7的整数倍；
现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
Input
输入数据的第一行是case数T(1 <= T <=
50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <=
10^18)。
Output
请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。
Sample Input
3
1 9
10 11
17 17
Sample Output
236
221
0
Recommend
Solution
数位dp
这道题有点麻烦，要求与7无关的数的平方和
可以先考虑求和，假设到了第i位，这一位枚举的数是o，搜索得到该情况下数的个数为num，那么这一位对和的贡献为num*o*10i-1,
然后就考虑平方啦
可以先看一看一个数的情况
按照a1*10i+a2*10i-1+...这种形式，可以把一个数看成很多数相加得到
设a1*10i=b1, a2*10i-1+...=b2
那么这个数的平方和为:
(b1+b2)2=b12+2*b1*b2+b22
题目中的问题，是有很多种b2(因为第一位为a1的满足条件的数可能有很多个)
可能是c1,c2,c3...(意义同b2)
要求b12+2*b1*c1+c12
b12+2*b1*c2+c22
b12+2*b1*c3+c32
即3*b12+2*b1*(c1+c2+c3)+c12+c22+c32
假设后面部分的和为sum，有num种情况
那么表示出来就是
num*b12+2*sum*b1+c12+c22+c32 (由于有多种情况，所以c12+c22+c32要递归求解)
所以我记录了三个值，dp[i][j][k].nu/su/sq表示考虑到第i位，每位数相加后模7为j，当前值模7为k的方案数，所有方案的数的和，所有方案的数的平方和
但是我有一个奇怪的问题，计算第二维的时候，如果每一次用上一位*10+这一位的值就A啦，但是如果每一次加上这一位在原数中所代表的值，就会在大数据的时候WA
希望哪个大佬可以告诉我为什么(☆▽☆)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define lo long long
#define mod 1000000007
using namespace std;
int a[23];
lo mi[41]; //mi[i]:10的i次幂
inline lo read()
{
register long long ans=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {ans=ans*10+ch-'0';ch=getchar();}
return ans*f;
}
struct num{
lo su,sq,nu; //和，平方和，个数
num(lo u=0,lo q=0,lo n=0):su(u),sq(q),nu(n){}
}dp[23][11][11];
num dfs(int wi,int o,lo e,bool lim) //哪一位，每一位%7，数%7，限制？
{
num ans,zc;
if(wi<1)
{
ans.nu=o&&e;
return ans;
}
if(!lim&&dp[wi][o][e].su>-1)
return dp[wi][o][e];
int l=lim? a[wi]:9;
for(lo i=0;i<=l;i++)
if(i!=7) //////
{
zc=dfs(wi-1,(o+i)%7,(lo)(e*10+i)%7,lim&&i==a[wi]); //e+i*mi[wi-1]?
ans.sq=(((ans.sq+i*i*mi[2*wi-2]%mod*zc.nu%mod)%mod+zc.sq)%mod+(lo)2*zc.su*i%mod*mi[wi-1]%mod)%mod;
ans.su=((ans.su+zc.su)%mod+zc.nu*i%mod*mi[wi-1]%mod)%mod;
ans.nu=(ans.nu+zc.nu)%mod;
}
if(!lim)
dp[wi][o][e]=ans;
return ans;
}
lo sol(lo x)
{
int w=0;
while(x)
{
a[++w]=x%10;
x/=10;
}
num ans=dfs(w,0,(lo)0,1);
return ans.sq;
}
int main()
{
int t;lo l,r;
t=read();
mi[0]=1;
for(int i=1;i<=38;i++)
mi[i]=mi[i-1]*10%mod;
memset(dp,-1,sizeof(dp));
while(t--)
{
l=read();r=read();
lo rr=sol(r);
lo ll=sol(l-1);
printf("%lld
",(rr+mod-ll)%mod);
}
return 0;
}