또 한 번 비트DP 물문제.

Description

구간 [a, b]에 1을 포함하는 수량을 구합니다.예를 들어 구간[111112]은 전체 구간에 두 개의 수를 포함하는데 각각 11112111은 3개의 1을 포함하고 112는 2개의 1을 포함하기 때문에 구간[11112]은 모두 5개를 포함한다.

Input

다중 테스트 데이터.
각 그룹의 테스트 데이터는 두 개의 정수 a, b, 1 <=a <=b <=10^18을 포함한다.

Output

각 그룹의 테스트 출력은 한 줄로 1의 수량을 표시하고 결과mod 10^9+7.

Sample Input

111 112
1 1000

Sample Output

5
301
 
 
코드는 다음과 같습니다.

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

const int MOD = int(1e9)+7;
typedef long long LL;
LL f[20]; // f[i]     i ，  1   
int bit[20];
LL num;

LL _pow(int b) {
    LL ret = 1;
    for (int i = 0; i < b; ++i) {
        ret *= 10;
    }
    return ret;
}

LL dfs(int p, int e) {
    if (p == -1) return 0;
    if (!e && f[p]!=-1) return f[p];
    LL ret = 0;
    int LIM = e ? bit[p] : 9;
    for (int i = 0; i <= LIM; ++i) {
        if (i == 1) {
            ret += dfs(p-1, e&&(i==LIM));
            ret %= MOD;
            if (e&&(i==LIM)) {
                ret += (num % _pow(p) + 1)%MOD;
                ret %= MOD;
            } else {
                ret += _pow(p) % MOD;
                ret %= MOD;
            }
        } else {
            ret += dfs(p-1, e&&(i==LIM));
        }
    }
    if (!e) {
        f[p] = ret;
    }
    return ret;
}

int cal(LL x) {
    if (!x) return 0;
    num = x;
    int idx = 0;
    while (x) {
        bit[idx++] = x % 10;
        x /= 10;
    }
    return dfs(idx-1, 1);
}

int main() {
    LL a, b;
    memset(f, 0xff, sizeof (f));
    while (scanf("%lld %lld", &a, &b) != EOF) {
        printf("%d
", (cal(b)-cal(a-1)+MOD)%MOD);
    }
    return 0;
}