hdu 4507 吉哥系列故事——恨7不成妻(數位DP)

NO IMAGE
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無關的數字的平方和。

 

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
 思路:dp[len][sum0][sum1] 表示長度為len對7取模為sum1,各位上的數字和取模為sum0有多少個滿足的數;
唯一麻煩的是和7無關的數字的平方和,當我們進行位的搜尋時需要用到以下方程;
對於一個數的平方和來講:(pre*10^pos   next)^2= (pre*10^pos)^2 2*pre*10^pos*next  next^2  
pre表示當前位,next表示下一位;
由於要記憶化,我們根據以上可以推出:
∑(Y xi)^2 = ∑(Y^2
2 * Y * xi xi^2) = n * Y^2 2 * Y * ∑xi ∑ xi^2   
程式碼:
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL mod=1e9 7;
int b[20];
LL n,m,p[20];
struct node{
LL cnt,sum,sqsum;
}dp[20][10][10];
node dfs(int len,int sum0,int sum1,int flag)
{
if(len==0)
{
node str;
str.cnt=(sum0!=0&&sum1!=0);
str.sqsum=0;
str.sum=0;
return str;
}
if(!flag&&dp[len][sum0][sum1].cnt!=-1)
return dp[len][sum0][sum1];
int end=flag?b[len]:9;
node now,next;
now.cnt=now.sqsum=now.sum=0;
for(int i=0;i<=end;i  )
{
if(i==7)
continue;
next=dfs(len-1,(sum0 i)%7,(sum1*10 i)%7,flag&&i==end); 
now.cnt =next.cnt%mod;  
now.sum =(next.sum next.cnt*i%mod*p[len-1]%mod)%mod; //求出已經搜尋完的數的總值
now.sum%=mod;
now.sqsum =(next.sqsum 2*next.sum%mod*i%mod*p[len-1]%mod)%mod;
now.sqsum%=mod;
now.sqsum =i*i*p[len-1]%mod*p[len-1]%mod*next.cnt%mod;
now.sqsum%=mod;
}
if(!flag)
dp[len][sum0][sum1]=now;
return now;
}
LL solve(__int64 n)
{
int len=0;
while(n)
{
b[  len]=n%10;
n=n/10;
}
return dfs(len,0,0,1).sqsum;
}
int main()
{
int t;
p[0]=1;
for(int i=1;i<20;i  )
p[i]=p[i-1]*10%mod;
for(int i=0; i<20; i  )
{
for(int j=0; j<10; j  )
{
for(int k=0; k<10; k  )
{
dp[i][j][k].cnt=-1;
}
}
}
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&m);
printf("%I64d\n",((solve(m)-solve(n-1) mod)%mod));
}
}