又一道按位DP水题

Description

求区间[a,b]包含1的数量。例如区间[111,112], 整个区间包含两个数，分别为111,112，111包含3个1，而112包含2个1，所以区间[111,112]总共包含5个1.

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\n", (cal(b)-cal(a-1)+MOD)%MOD);
    }
    return 0;
}