ABC295F数位DP等价转换状态压缩

填到第k位，填的是v，记忆化绝对没错，只是v太大！！！
核心：不管v多大，对后面的影响就是，当前已经匹配到多少次？当前的结尾对后面有什么影响？
匹配次数可以算出来，当前结尾对后面有影响，前提是他是匹配串的前缀！因为需要新增一个匹配，则结尾这一段必然是匹配串的前缀，且长度越长越好。
细节：另外需要考虑，后面还受是否可以随便填、是否全是前导零的影响。

#include <bits/stdc++.h>
#define LL long long
#define N 18
using namespace std;
LL t, n, m, i, j, k, l, r, a[N], f[N][N][N][2][2];
char s[N], ss[N];
void duo(LL v, LL &x, LL &y){
    memset(ss, x=y=0, sizeof(ss));
    sprintf(ss, "%lld", v);
    LL i, c=strlen(s), d=strlen(ss);
    for(i=0; i+c<=d; i++){
        if(strncmp(s, ss+i, c) == 0) y++;
    }
    for(i=1; i<=c&&i<=d; i++){
        if(strncmp(s, ss+d-i, i) == 0) x = i;
    }
}
LL dfs(LL k, LL v, LL p){
    LL i, j, x, y, s=0, u=p?9:a[k];//后面是否可以随便填p
    duo(v, x, y);//将v进行状态压缩：有多少个贡献y，结尾是多少x
    if(k == 0) return y;
    if(~f[k][x][y][p][v>0]) return f[k][x][y][p][v>0];
    for(i=0; i<=u; i++){
        s += dfs(k-1, v*10+i, p||i<a[k]);
    }//是否全是0，用v>0表示
    return f[k][x][y][p][v>0] = s;
}//填到第k位，填的是v，记忆化绝对没错，只是v太大！！！
LL cal(LL x){
    memset(f, -1, sizeof(f));
    n = x, k = 0;
    while(x) a[++k] = x%10, x /= 10;
    return dfs(k, 0, 0);
}
int main(){
    scanf("%lld", &t);
    while(t--){
        scanf("%s%lld%lld", s, &l, &r);
        printf("%lld\n", cal(r)-cal(l-1));
    }
    return 0;
}

数位DP优化：

#include <bits/stdc++.h>
#define LL long long
#define N 18
using namespace std;
LL t, n, m, i, j, k, l, r, a[N], f[N][N][N];
char s[N], ss[N];
void duo(LL v, LL &x, LL &y){
    memset(ss, x=y=0, sizeof(ss));
    sprintf(ss, "%lld", v);
    LL i, c=strlen(s), d=strlen(ss);
    for(i=0; i+c<=d; i++){
        if(strncmp(s, ss+i, c) == 0) y++;
    }
    for(i=1; i<=c&&i<=d; i++){
        if(strncmp(s, ss+d-i, i) == 0) x = i;
    }
}
LL dfs(LL k, LL v, LL p){
    LL i, j, x, y, s=0, u=p?9:a[k];
    duo(v, x, y);
    if(k == 0) return y;
    if(p && v && ~f[k][x][y]) return f[k][x][y];
    for(i=0; i<=u; i++){
        s += dfs(k-1, v*10+i, p||i<a[k]);
    }
    if(p && v) f[k][x][y] = s;//前面全相等、全是0没必要记忆化
    return s;
}
LL cal(LL x){
    n = x, k = 0;
    while(x) a[++k] = x%10, x /= 10;
    return dfs(k, 0, 0);
}
int main(){
    scanf("%lld", &t);
    while(t--){
        scanf("%s%lld%lld", s, &l, &r);
        memset(f, -1, sizeof(f));//优化后只需要memset一次，因为匹配串不同，不可放外面
        printf("%lld\n", cal(r)-cal(l-1));
    }
    return 0;
}