hdu4507 吉哥系列故事——恨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无关的数字的平方和。

输入数据的第一行是case数T(1 <= T <= 50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。

请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。

  
3
1 9
10 11
17 17

  
236
221
0
这一题我们可以看出，要求是很多的，这里很容易从数据大小和时限可以看出是必须用dp做的，要求不和７相关的平方和，对于问题要求解的是符合的数的平方和。这个是最关键的。为了维护平方和的信息，我们可以这样做，定义一个结构，node cnt存当前符合的总个数，s1存符合条位的和，s2存符合条位的平方各。如果，当前位是i 长度是len,那么所有符合条件的和就是sum(i * 10^len + b)^2  这里的b就是所有符合条件的尾数。
这样直接求当然不可求，那么就要拆开求解，因为每一个符合条件的数都会有个(i * 10^len)^2这个数，所以直接加在一起就是cnt * (i * 10^len)^2
sum{b^2}自然就是下一位的s2了，还有sum(2 * i * 10^len * b),可以转化成2 * 10^len * sum1,这里sum1就是b的和，总的公式也就是
ans.s1=sum(temp.cnt*ktemp.s1); s1自然是各位数之和
ans.s2=sum(k*k*temp.cnt+k*temp.s1*2+temp.s2; s2就是上面讲的和
k = i * 10^len
这样，就可以统护所有的信息。因为所有的数可能爆__int64，所以都要取模。
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define M  100
int pri[M];
#define MOD 1000000007
struct node {__int64 cnt,s1,s2;node(__int64 tcnt=0,__int64 ts1=0,__int64 ts2=0){cnt=tcnt,s1=ts1,s2=ts2;}
}dp[M][7][7][3];
bool flag[M][7][7][3];
__int64 ten[30];
node dfs(int pos,int t,int s,int mod,int f){if(pos==0){if(t||mod==0||s==0)return node(0,0,0);return node(1,0,0);}if(!f&&flag[pos][s][mod][t])return dp[pos][s][mod][t];int u=f?pri[pos]:9;node ans;for(int i=0;i<=u;i++){node temp=dfs(pos-1,t||i==7,(s+i)%7,(mod*10+i)%7,f&&i==u);ans.cnt=(ans.cnt+temp.cnt)%MOD;__int64 k=i*ten[pos-1]%MOD;ans.s1=(temp.cnt*k%MOD+temp.s1+ans.s1)%MOD;ans.s2=(k*k%MOD*temp.cnt%MOD+k*temp.s1%MOD*2+temp.s2+ans.s2)%MOD;}if(!f)flag[pos][s][mod][t]=true,dp[pos][s][mod][t]=ans;return ans;
}
__int64 solve(__int64 x){int cnt=0;while(x){pri[++cnt]=x%10;x/=10;}node temp=dfs(cnt,0,0,0,1);return temp.s2;
}
int main()
{int tcase;__int64 l,r;memset(flag,false,sizeof(flag));ten[0]=1;for(int i=1;i<30;i++)ten[i]=ten[i-1]*10%MOD;scanf("%d",&tcase);while(tcase--){scanf("%I64d%I64d",&l,&r);printf("%I64d\n",(solve(r)-solve(l-1)+MOD)%MOD);}return 0;
}