Luogu 3413 SAC#1 - 萌数

挺好想的数位dp，直接上板。

然而要注意的一点就是我们在这一题中需要记录下前两位的值。记忆化的数组中记录的值必须要是两位以上的数，所以在记忆化的时候要再加上一句$pre2 != -1$，要不然状态记录下的值其实多数了一些，就会错。

时间复杂度$O(n * 10 * 10 * 2)$。

Code：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 1005;
const ll P = 1e9 + 7;

int a[N], b[N];
ll f[N][10][2];
char in[N];

inline void get(int *arr) {
    scanf("%s", in + 1);
    arr[0] = strlen(in + 1);
    for(int i = 1; i <= arr[0]; i++)
        arr[i] = in[arr[0] - i + 1] - 48;
}

ll dfs(int pos, int pre2, int pre1, bool has, bool lead, bool lim, int *bit) {
    if(pos == 0) return has;
    if(!lim && !lead && f[pos][pre1][has] != -1) 
        return f[pos][pre1][has];
    
    ll res = 0LL; int num = lim ? bit[pos] : 9;
    for(int i = 0; i <= num; i++) {
        if(lead) res = (res + dfs(pos - 1, -1, (i == 0) ? -1 : i, has, lead && (i == 0), lim && (i == bit[pos]), bit)) % P;
        else res = (res + dfs(pos - 1, pre1, i, has || (i == pre1) || (i == pre2), lead && (i == 0), lim && (i == bit[pos]), bit)) % P;
    }
    
    if(!lim && !lead && pre2 != -1) f[pos][pre1][has] = res;
    return res;
}

inline ll solve(int *arr) {
    memset(f, -1LL, sizeof(f));
    ll res = dfs(arr[0], -1, -1, 0, 1, 1, arr);
    return res;
}

int main() {
    get(a), get(b);
    
    a[1]--;
    for(int i = 1; i < a[0]; i++)
        if(a[i] < 0) a[i] += 10, a[i + 1]--;
    for(; a[a[0]] == 0 && a[0] > 0; --a[0]);
    
/*    for(int i = 1; i <= a[0]; i++) printf("%d", a[i]);
    printf("\n");    */
    ll resB = solve(b), resA = solve(a);
//    printf("%lld %lld\n", resB, resA);
    printf("%lld\n", (resB - resA + P) % P);
    return 0;
}