hdu 4507 길 고 시리즈 - 7 불 성 처 를 미워 하 는 DP

지 고 시리즈 - 7 불 성 처 를 미워 하 다.
Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1964    Accepted Submission(s): 569
Problem Description
싱글!
여전히 솔로!
길 형 은 여전히 솔로!
DS 급 우리 길 형 은 여전히 솔로!
그래서 그 는 평생 발 렌 타인 데 이 를 가장 미워 했다. 214 든 77 이 든 모두 싫어 했다!
　　
길 고 는 214 와 77 이라는 두 수 를 관찰 한 결과:
　　2+1+4=7
　　7+7=7*2
　　77=7*11
결국 그 는 이 모든 것 이 7 과 관련 이 있 기 때 문 이라는 것 을 알 게 되 었 다.그래서 그 는 지금 7 과 관련 된 모든 숫자 를 싫어한다!
어떤 숫자 가 7 과 관련 이 있 습 니까?
만약 하나의 정수 가 아래 세 가지 조건 중 하나 에 부합된다 면, 우 리 는 이 정수 가 7 과 관계 가 있다 고 말 할 것 이다.
1. 정수 중 한 명 은 7 이다.
2. 정수 의 한 사람 당 합 친 것 은 7 의 정수 배 이다.
3. 이 정 수 는 7 의 정수 배 이다.
지금 문제 가 생 겼 다. 길 형 은 일정 구간 내 에서 7 과 무관 한 숫자의 제곱 합 을 알 고 싶 어 한다.
 
Input
입력 한 데이터 의 첫 줄 은 case 수 T (1 < = T < = 50) 이 고 다음 T 줄 은 T 개의 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
   
   
   
   

  [L, R] 내 모든 만족 조건 의 수의 제곱 합 은 얼마 입 니까?
  이 문 제 는 좀.제곱 합 을 어떻게 구 하 느 냐 에 중점 을 두다.
  유지 보수 의 dp 값 은 하나 가 아 닙 니 다. 3 개, dp [cur] [sum 1] [sum 2] 의 a, a2, n 을 유지 해 야 합 니 다.현재 cur 위치 로 처 리 된 것 을 의미 합 니 다. 앞의 수 mod7 = sum 1, 앞의 숫자 와 mod7 = sum 2 입 니 다. 이 상태 에서 뒤의 모든 만족 하 는 수치, 뒤의 이 비트 의 합 은 a 이 고 제곱 과 a2 이 며 모두 n 개의 수 입 니 다.a, a2, n 에 따라 현재 a ', a2', n '을 내 놓 을 수 있 습 니 다.현재 이 분 이 i 를 가 져 오 면 a '+ = i * 10 ^ cur * n + a, a2' + = (10 ^ cur) ^ 2 * i ^ 2 * n + 2 * 10 ^ cur * i * a + a2, n '+ = n.
 

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;

typedef long long LL;

const int MAXN=70;
const LL MOD=1000000007;

int T;
LL L,R;
int bit[MAXN];
bool vis[MAXN][10][10];
LL power[20];

struct DP{
    LL a,a2,n;
}dp[MAXN][10][10];

DP dfs(int cur,int sum1,int sum2,int e){
    if(cur<0){
        if(sum1%7&&sum2%7) return (DP){0,0,1};
        return (DP){0,0,0};
    }
    if(!e&&vis[cur][sum1][sum2]) return dp[cur][sum1][sum2];
    int end=e?bit[cur]:9;
    LL b=0,b2=0,n=0;
    DP tmp;
    for(int i=0;i<=end;i++) if(i!=7){
        tmp=dfs(cur-1,(sum1*10+i)%7,(sum2+i)%7,e&&i==end);
        if(tmp.n>0){
            b=(b+(i*power[cur])%MOD*tmp.n%MOD+tmp.a)%MOD;
            b2=(b2+((power[cur]*power[cur]%MOD*i*i)%MOD*tmp.n%MOD+(2*power[cur]*i%MOD*tmp.a)%MOD+tmp.a2)%MOD)%MOD;
            n=(n+tmp.n)%MOD;
        }
    }
    if(!e){
        vis[cur][sum1][sum2]=1;
        dp[cur][sum1][sum2]=(DP){b,b2,n};
    }
    return (DP){b,b2,n};
}

LL solve(LL n){
    int len=0;
    while(n){
        bit[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,0,0,1).a2;
}

int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&T);
    power[0]=1;
    for(int i=1;i<=18;i++) power[i]=(power[i-1]*10)%MOD;
    memset(vis,0,sizeof(vis));
    while(T--){
        scanf("%I64d%I64d",&L,&R);
        printf("%I64d
",(solve(R)-solve(L-1)+MOD)%MOD);
    }
    return 0;
}